BZOJ 2096: [Poi2010]Pilots( set )

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

上一篇:微信小程序未来怎么样?听微盟卫晓祥来说说


下一篇:PHP学习笔记 - 入门篇(5)