HDU 5289 尺取

Assignment

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 4316 Accepted Submission(s): 1984

Problem Description

Tom owns a company and he is the boss. There are n staffs which are numbered from 1 to n in this company, and every staff has a ability. Now, Tom is going to assign a special task to some staffs who were in the same group. In a group, the difference of the ability of any two staff is less than k, and their numbers are continuous. Tom want to know the number of groups like this.

Input

In the first line a number T indicates the number of test cases. Then for each case the first line contain 2 numbers n, k (1<=n<=100000, 0<k<=10^9),indicate the company has n persons, k means the maximum difference between abilities of staff in a group is less than k. The second line contains n integers:a[1],a[2],…,a[n](0<=a[i]<=10^9),indicate the i-th staff’s ability.

Output

For each test，output the number of groups.

Sample Input

2
2
1 2 4
5
3 4 5 2 1 6 7 8 9

Sample Output

5
28
Hint

First Sample, the satisfied groups include:[1,1]、[2,2]、[3,3]、[4,4] 、[2,3]

Author

FZUACM

Source

2015 Multi-University Training Contest 1

题目大意是给出一个长度为N的数组，定义f(l,r)=MAX{ai | l<=i<=r}-MIN{ai | l<=i<=r}

给出个k值，求有多少个不同的(l,r)使得 f(l,r)<k

之所以找到这道源于今天玲珑的一道B，别人说是HDU原题，所以找到看看。

比赛时我想到的就是从没没实战过得尺取法，自认为没问题，却一直WA，当然最后发现是a[maxn],a[minn]手贱打成了maxn,minn,

由于样例太弱以至于没看出来，可惜本来可以A两道题的。

存在更有的对数级算法，涉及到不熟练的ST类算法，日后再看看吧。

正文:

对于我们要寻找这个区间[l,r]，我们不妨先把r固定住然后找到l的最大范围，接着统计一下加上去，

这个思路的正确性在于，当固定住r时，往左一直走，走到一个不满足条件的位置时，显然其往左的所有位置都是非法的,

换句话说当区间[l,r]不满足条件时，所有大于等于这个区间的区间都不会满足条件。

当然您也可以固定住l，大同小异。

每当循环到一个r时，会出现两种情况，一是加入a[r]之后当前的尺子仍满足条件，我们维护一个L表示尺子的最左端，此时应执行s+=i-L;

二是加入这个元素之后尺子不满足条件了，为了使尺子再次满足条件，我们需要对L进行操作，找到一个最小的L使其再次满足条件，

显然L最差就是这个位置，即L=r，此时得差值为0一定<k,循环完所有的r,输出答案即可。

用了scanf，280ms水过也不算很慢

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long
 4 #define eps 1e-12
 5 int a[200005];
 6 int main()
 7 {
 8     int n,k,i,t,j;
 9     LL s=0;
10     cin>>t;
11     while(t--){s=0;
12     cin>>n>>k;
13     for(i=1;i<=n;++i) scanf("%d",&a[i]);
14     s=n;
15     int maxn=1,minn=1,l=1;
16     for(i=1;i<=n;++i){
17         if(a[i]>=a[maxn]) maxn=i;
18         if(a[i]<=a[minn]) minn=i;
19         if(a[maxn]-a[minn]<k)
20         {
21            s+=i-l;
22         }
23         else
24         {
25             maxn=minn=i;
26             for(j=i;j>=1;--j)
27             {
28                 if(a[j]>=a[maxn])
29                 {
30                  if(a[j]-a[minn]>=k) break;
31                  else maxn=j;
32                 }
33                 if(a[j]<=a[minn])
34                 {
35                  if(a[maxn]-a[j]>=k) break;
36                  else minn=j;
37                 }
38 
39             }
40         l=j+1;
41         s+=i-l;
42         }
43     }cout<<s<<endl;
44     }
45     return 0;
46 }