1<=n<= 106
Ans=min(max(|ai−aj|,j−i+1)) 假设我们现在的区间长度是m，最小值是min，将右端点右移，m++，min将可能会减小。 我们确定一个左端点l，假设右端点是r，那么一定当r位于m>=min的临界点上max(m, min)菜会最小。 证明：假设现在在临界点上,r–,则m–，min可能增加，答案不可能减少。r++，m++，min可能减少，答案不可能减少。 所以我们从[1..2]开始，如果m >= min，则r++，否则l++。 本来用multiset维护min就行了，可是卡时太惨了，反而用线段树还快一些。
Code：
#include<cstdio> #include<cstring> #include<algorithm> #define fo(i, x, y) for(int i = x; i <= y; i ++) #define max(a, b) ((a) > (b) ? (a) : (b)) #define min(a, b) ((a) < (b) ? (a) : (b)) #define abs(a) ((a) > 0 ? (a) : -(a)) using namespace std; const int Maxn = 1e6 + 5; int n, ans, a[Maxn], num[Maxn], v[Maxn], tot; struct node { int x, y; }b[Maxn]; struct tree { int l, r, s, siz; }t[Maxn * 10]; void read(int &x) { char ch = ' '; for(; ch < '0' || ch > '9'; ch = getchar()); x = 0; for(;ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48; } bool rank(node a, node b) { return a.x < b.x; } void Init() { scanf("%d", &n); fo(i, 1, n) read(a[i]), b[i].x = a[i], b[i].y = i; sort(b + 1, b + n + 1, rank); tot = 0; fo(i, 1, n) tot += b[i].x != b[i - 1].x, num[b[i].y] = tot, v[tot] = b[i].x; } void add(int i, int x, int y, int l, int r) { if(x == y) { t[i].siz += r; if(t[i].siz) t[i].l = t[i].r = x; else t[i].l = t[i].r = 0; if(t[i].siz > 2) t[i].s = 0; else t[i].s = 2e9; } else { int m = (x + y) / 2; if(l <= m) add(i + i, x, m, l, r); else add(i + i + 1, m + 1, y, l, r); t[i].s = min(t[i + i].s, t[i + i + 1].s); if(t[i + i].r && t[i + i + 1].l) t[i].s = min(t[i].s, v[t[i + i + 1].l] - v[t[i + i].r]); t[i].l = t[i + i].l; if(t[i].l == 0) t[i].l = t[i + i + 1].l; t[i].r = t[i + i + 1].r; if(t[i].r == 0) t[i].r = t[i + i].r; } } void End() { fo(i, 1, tot * 10) t[i].s = 2e9; add(1, 1, tot, num[1], 1); add(1, 1, tot, num[2], 1); ans = 1e9; int l = 1, r = 2; while(r <= n) { int z = t[1].s; ans = min(ans, max(z, r - l + 1)); if(l == r - 1 || t[1].s > r - l + 1) { if(r == n) break; r ++; add(1, 1, tot, num[r], 1); } else add(1, 1, tot, num[l], -1), l ++; } printf("%d", ans); } int main() { Init(); End(); }