用个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
5 1 3 5 8 6 6 9 10
Sample Output
4
（有两个子串的长度为4: 5, 8, 6, 6 和8, 6, 6, 9.最长子串的长度就是4）
（有两个子串的长度为4: 5, 8, 6, 6 和8, 6, 6, 9.最长子串的长度就是4）