leetcode 209. Minimum Size Subarray Sum (尺取法)

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint

 

思路:尺取即可。。好久没写,竟然调了半天。。。

 

BZOJ 1800: [Ahoi2009]fly 飞行棋 (尺取+数学)

 

1800: [Ahoi2009]fly 飞行棋

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 1530  Solved: 1220
[Submit][Status][Discuss]

Description

给出圆周上的若干个点,已知点与点之间的弧长,其值均为正整数,并依圆周顺序排列。 请找出这些点中有没有可以围成矩形的,并希望在最短时间内找出所有不重复矩形。

Input

第一行为正整数N,表示点的个数,接下来N行分别为这N个点所分割的各个圆弧长度

Output

所构成不重复矩形的个数

Sample Input

8
1
2
2
3
1
1
3
3
 

Sample Output

3

HINT

N<= 20

思路:一开始的想法是枚举四条边,如果a==c&&b==d,就认为是找到了一个矩形。

重点在于判重,非常不好判断。一开始想要根绝四条边的长度hash一下,但是设想一个所有弧长都相等,且弧长较多的情况。

此时所有矩形的边长长度都相同,但是显然是不同的矩形,因此这种判断方法是错误的。

比较棒的思路是:矩形的对角线一定是外接圆的直径。

因此只需要找有多少条执行,假设为c,那么答案就是c*(c-1)/2(因为任意两条对角线就可以构成一个矩形)

这种做法的好处很明显,不需要判重。

至于如何找直径,直径是把圆周等分的弦,所以尺取找一下就好了。

复杂度O(n)

 

codeforces 220 E. Little Elephant and Inversions (树状数组+尺取)

题目链接

题意:

how many pairs of integers l and r are there, such that 1 ≤ l < rn and sequence b = a1a2alarar + 1an has no more than k inversions.

我花了两个小时才看懂题。。。。一直没懂b数列中a[l]和a[r]怎么就挨着了。。。

其实意思是。。。只保留a数列中1..l和r..n的。。。构成b数列。。。然后b数列的逆序对数小于等于k.问这样的l,r的对数。

思路:尺取+树状数组。

枚举l,每次找到最小的满足题意的r,对答案的贡献是n-r+1,然后用两个树状数组,分别维护增加或者减少一个树的时候,前半段和后半段对逆序数的影响。

 

 

hdu 4123 Bob’s Race (树的直径+尺取+rmq)(珍爱生命,远离log)

hdu 4123 题目链接

 

题意:一棵树,定义d[i]为点i到树上某点的最大距离。。。给出若干查询,每个查询一个x,问最多能有多少点满足这些点中,最大的d与最小的d的差小于等于x.要求这些点的编号必须是连续的。

思路:可以三遍bfs处理出所有点的d…

由于不能排序。。。所以就是尺取+rmq….

然而神Tm TLE…..

这复杂度还TLe…

结果最后发现是。。。log运算的常数太大被卡。。。

2016-07-17 23-19-46 的屏幕截图 2016-07-17 23-26-58 的屏幕截图

 

所以做法是先预处理一下。。。嗯。。。。

 

珍爱生命,远离log!

珍爱生命,远离log!

珍爱生命,远离log!

 

 

 

codeforces 660 C. Hard Process (ruler)

cf660C

solution:ruler.1A

 

hdu 3530 Subsequence (尺取+rmq)

hdu 3530题目链接

题意:给出n个数,m,k,问最大的j-i+1,使得【i,j】间的最大值与最小值的差属于[m,k]
思路:rmq+尺取。 2A.

codeforces 279 B books

http://codeforces.com/problemset/problem/279/B
题意:给定一个序列,问一段连续的序列的和小于等于t的最长的序列的长度。
思路:尺取法。三个月前学习的了。

codeforces #321 div 2 B. Kefa and Company(尺取法)

B. Kefa and Company
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Kefa wants to celebrate his first big salary by going to restaurant. However, he needs company.

Kefa has n friends, each friend will agree to go to the restaurant if Kefa asks. Each friend is characterized by the amount of money he has and the friendship factor in respect to Kefa. The parrot doesn’t want any friend to feel poor compared to somebody else in the company (Kefa doesn’t count). A friend feels poor if in the company there is someone who has at least d units of money more than he does. Also, Kefa wants the total friendship factor of the members of the company to be maximum. Help him invite an optimal company!

Input

The first line of the input contains two space-separated integers, n and d (1 ≤ n ≤ 105, ) — the number of Kefa’s friends and the minimum difference between the amount of money in order to feel poor, respectively.

Next n lines contain the descriptions of Kefa’s friends, the (i + 1)-th line contains the description of the i-th friend of type misi(0 ≤ mi, si ≤ 109) — the amount of money and the friendship factor, respectively.

Output

Print the maximum total friendship factir that can be reached.

Sample test(s)
input

output

input

output

Note

In the first sample test the most profitable strategy is to form a company from only the second friend. At all other variants the total degree of friendship will be worse.

In the second sample test we can take all the friends.

 

尺取直接搞…

然后因为没开longlong wa了一发…

因为看错条件,money差值等于d也会被鄙视...所以不能取等号…

都是傻逼错误…药丸,药丸啊…

poj 2566 Bound Found (前缀和,尺取法(two pointer))

题意 :给定一个长度为n的区间.然后给k次询问,每次一个数t,求一个区间[l,r]使得这个区间和的绝对值最接近t

没办法直接尺取.

先预处理出来前缀和

如果要找一对区间的和的绝对值最最近t

等价于找到两个数i和j,使得sum[i]-sum[j]的绝对值最接近t,且i<>j

那么对前缀和排序…然后尺取

因为答案要输出下标

所以之前先存一下下标.

然后对于i,j

所对应的区间为[min(pre[i].id,pre[j].id)+1,max(pre[i],id,pre[j].id)];

poj 3320 Jessica’s Reading Problem (尺取法)

Jessica’s Reading Problem
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 8787   Accepted: 2824

Description

Jessica’s a very lovely girl wooed by lots of boys. Recently she has a problem. The final exam is coming, yet she has spent little time on it. If she wants to pass it, she has to master all ideas included in a very thick text book. The author of that text book, like other authors, is extremely fussy about the ideas, thus some ideas are covered more than once. Jessica think if she managed to read each idea at least once, she can pass the exam. She decides to read only one contiguous part of the book which contains all ideas covered by the entire book. And of course, the sub-book should be as thin as possible.

A very hard-working boy had manually indexed for her each page of Jessica’s text-book with what idea each page is about and thus made a big progress for his courtship. Here you come in to save your skin: given the index, help Jessica decide which contiguous part she should read. For convenience, each idea has been coded with an ID, which is a non-negative integer.

Input

The first line of input is an integer P (1 ≤ P ≤ 1000000), which is the number of pages of Jessica’s text-book. The second line contains P non-negative integers describing what idea each page is about. The first integer is what the first page is about, the second integer is what the second page is about, and so on. You may assume all integers that appear can fit well in the signed 32-bit integer type.

Output

Output one line: the number of pages of the shortest contiguous part of the book which contains all ideals covered in the book.

Sample Input

Sample Output

分类: C/C++

 

转载一段讲解
 
     我们先来介绍一下尺取法。尺取法,顾名思义,像尺子一样,一块一块的截取。是不是解释的有点让人纳闷~。。没关系,下面我们通过这个题目来体会尺取法的魅力。

 

题目翻译:

  给定长度为n的数列整数a0,a1,a2,a3 ….. an-1以及整数S。求出综合不小于S的连续子序列的长度的最小值。如果解不存在,则输出0。

 

  限制条件:

    10

    0

    S<10^8

 

这里我们拿第一组测试数据举例子,即 n=10, S = 15, a = {5,1,3,5,10,7,4,9,2,8}

 

   这幅图便是尺取法怎么“取”的过程了。

  整个过程分为4布:

    1.初始化左右端点

    2.不断扩大右端点,直到满足条件

    3.如果第二步中无法满足条件,则终止,否则更新结果

    4.将左端点扩大1,然后回到第二步

 

用尺取法来优化,使复杂度降为了O(n)。

最后,再给一个尺取法的定义以便更好理解:返回的推进区间开头和结尾,求满足条件的最小区间的方法称为尺取法。

以上为网上关于尺取法的原理介绍,还是比较好理解的,邢如蚯蚓的爬动。

 

 

  然后这道题可以先用set ,统计出不同的知识点有多少个,总是记为total

  然后根据一段区间内的知识点数目sum是否达到total来移动两个pointer head 和tail

  因为知识点的标号比较大,数组下表存不下,所以开个map来统计相应知识点出现的数量…

  然后还有个...

  误以为if (cnt[a[tail++]]++==0) sum++;和

  if (cnt[a[tail]]==0)

  {

    sum++;

    cnt[a[taill]]++;

    tail++;

  }

  是等价的...

幸好没去队群里问...不然又要被嘲讽一番了..

区别在于.前者无论cnt[a[tail]]是否为0,tail和cnt都会++;

而后者..只有在cnt[a[tail]]为0时,tail和cnt才会++