BZOJ 2096: [Poi2010]Pilots( set )

用个set维护就可以水过去...O(NlogN)

应该可以用单调队列O(N)....

----------------------------------------------------------------------

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

using namespace std;

const int maxn = 3000009;

int lim, N, seq[maxn];

multiset<int> S;

multiset<int> :: iterator It[maxn];

int main() {

scanf("%d%d", &lim, &N);

for(int i = 0; i < N; i++)

scanf("%d", seq + i);

S.clear();

It[0] = S.insert(seq[0]);

int ans = 0, p = 0;

for(int i = 1; i < N; i++) {

for(; ;) {

set<int> :: iterator Min = S.begin(), Max = S.end();

if(Min == Max) break;

if(abs(seq[i] - *Min) <= lim && abs(seq[i] - *--Max) <= lim) break;

S.erase(It[p++]);

}

It[i] = S.insert(seq[i]);

ans = max(ans, i - p + 1);

}

if(N == 1)

puts("1");

else

printf("%d\n", ans);

return 0;

}

----------------------------------------------------------------------

2096: [Poi2010]Pilots

Time Limit: 30 Sec Memory Limit: 162 MB
Submit: 492 Solved: 255
[Submit][Status][Discuss]

Description

Tz又耍畸形了！！他要当飞行员，他拿到了一个飞行员测试难度序列，他设定了一个难度差的最大值，在序列中他想找到一个最长的子串，任意两个难度差不会超过他设定的最大值。耍畸形一个人是不行的，于是他找到了你。

Input

输入：第一行两个有空格隔开的整数k（0<=k<=2000,000,000），n(1<=n<=3000,000)，k代表Tz设定的最大值，n代表难度序列的长度。第二行为n个由空格隔开的整数ai（1<=ai<=2000,000,000），表示难度序列。

Output

输出：最大的字串长度。

Sample Input

3 9
5 1 3 5 8 6 6 9 10

Sample Output

4
（有两个子串的长度为4: 5, 8, 6, 6 和8, 6, 6, 9.最长子串的长度就是4）

HINT

Source

by poi

巴特西