JZOJ – 100036 随机

Time Limit : 2000ms
Memory Limit : 256MB

Sample Input

5
9 20 15 6 10


Sample Output

4


代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>

using namespace std;
const int MAXN = 1000000 + 10;

multiset <int> data, val;
multiset <int> :: iterator q, after, before;

int input[MAXN];
int n;
int ans = 0x3f3f3f3f;
int l, r;

int main(){

freopen("random.in", "r", stdin);
freopen("random.out", "w", stdout);

scanf("%d", &n);

for(register int i=1; i<=n; i++)
scanf("%d", &input[i]);

l = 1, r = 2;

data.insert(input[1]);
data.insert(input[2]);
val.insert(abs(input[2] - input[1]));

while(r <= n){
int m = r - l + 1;

ans = min(ans, max(m, *val.begin()));

if(m < *val.begin() || m == 2){
if(r == n)
break;

r++;

data.insert(input[r]);
q = data.find(input[r]);

if(q == data.begin()){
after = q;
++after;

val.insert(*after - *q);
}else if((++q) == data.end()){
--q;
before = q;
--before;

val.insert(*q - *before);
}else{
--q;

before = q;
--before;
after = q;
++after;

val.erase(*after - *before);
val.insert(*q - *before);
val.insert(*after - *q);
}
}else{
q = data.find(input[l]);
l++;

if(q == data.begin()){
after = q;
++after;

val.erase(*after - *q);
}else if((++q) == data.end()){
--q;
before = q;
--before;

val.erase(*q - *before);
}else{
--q;

after = q;
before = q;
++after;
--before;

val.erase(*after - *q);
val.erase(*q - *before);
val.insert(*after - *before);
}
data.erase(q);
}
}

printf("%d\n", ans);
return 0;
}