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

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

程序员文章站 2022-03-31 19:10:37
...

题目

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

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

思路

水法

正解时不可能的,这辈子都不可能的

首先,我们发现选两个端点作为si,sj才是最优的。
所以我们可以枚举区间长度(i

#include<cstdio>
#include<cmath>
using namespace std;
int ans,n,a[1000077];
int main()
{
    freopen("random.in","r",stdin);
    freopen("random.out","w",stdout);
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    ans=n;
    for(int i=2; i<ans; i++)
    {
        for(int j=1; j+i<n; j++)
        {
            if(abs(a[j]-a[j+i-1])<ans) ans=abs(a[j]-a[j+i-1]);
        }
    }
    printf("%d",(ans>1?ans:2));
}

正解

啊,真香!

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

问题是,怎么维护?

我们可以开两个set,一个记录a[l..r] (s),一个记录(s1-s0,s2-s1…) (ss)

首先考虑加入一个数x。
设x在s中的位置为t,可以发现我们要把SS(St+1-St-1)删掉,再插入与其相邻的两个数。

然后考虑删除一个数x
与插入反过来,删掉相邻两个,插入一个。

我的程序玄学WA,但当个伪代码是可以的

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<set>
using namespace std;
const int maxn=1000077,inf=0x3f3f3f3f;
multiset<int> s,ss;
int n,a[maxn],ans;
int main()
{
//  freopen("random.in","r",stdin);
//  freopen("random.out","w",stdout);
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    int l=1,r=2;
    s.insert(a[1]); s.insert(a[2]); ss.insert(abs(a[1]-a[2]));
    ans=inf;
    multiset<int>::iterator si,ssi=ss.begin();
    while(r<=n&&l<r)
    {
        int t=*ssi,t1=r-l+1;
        ans=min(ans,max(t,t1));
        if(t>t1)
        {
            r++;
            s.insert(a[r]);
            si=s.find(a[r]);
            int x=*--si; si++; int y=*++si; si--;
            ss.erase(abs(x-y));
            ss.insert(abs(*si-*--si)); ss.insert(abs(*++si-*++si));
        }else
        {
            si=s.find(a[l]);
            ss.erase(abs(*si-*--si)); ss.erase(abs(*++si-*++si));
            int x=*si; si--; si--; int y=*si;
            ss.insert(abs(x-y));
            s.erase(a[l]); l++;
        }
    }
    printf("%d",ans);
}