JZOJ – 100036 随机

Time Limit : 2000ms
Memory Limit : 256MB

Description

Input

Output

Sample Input

5 
9 20 15 6 10

Sample Output

Data Constraint

解题思路

我们发现，随着区间长度的增长，$m$在不断变大，而$min |S_i – S_j| $在不断减小。

我们考虑区间 $[l, r]$，如果当前区间 $m$ 比 $min |S_i – S_j| $小，就说明需要增加 $m$ 减小 $min |S_i – S_j| $，将 $r+1$，否则则相反，将 $l+1$

我们还需要维护区间内元素 $min |S_i – S_j| $的最小值，考虑开两个 multiset，一个维护元素的值，一个维护元素相邻两个的差值

每次插入一个值 $b$，就将它插入第一个set，然后在第一个set中找到他的位置，并且找到他前一个$a$ 和后一个元素 $c$ 的值

那么在维护相邻两个元素差值的set中删除 $c-a$，依次插入 $b-a$ 和 $c-b$ 即可

注意特殊处理当 $b$ 的迭代器指向 $begin$ 和 $end-1$ 的情况

删除操作这是插入操作的逆过程，最小值即为第二个set的*begin

代码

#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;
}

[题解] JZOJ – 100036 随机

BLOG