欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

JZOJ 100036 【NOIP2017提高A组模拟7.10】随机

程序员文章站 2024-02-12 22:37:40
...

题目大意:

JZOJ 100036 【NOIP2017提高A组模拟7.10】随机
1<=n<=106

题解:

Ans=min(max(|aiaj|,ji+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();
}