BZOJ4123: [Baltic2015]Hacker

题解:

(题面有错误,每一次选的并不是与"上一次"选的元素相邻的元素,而是只要与选过的元素相邻就可以.)

考虑假如我们知道Alice第一个选的元素.

那么Alice最大能够拿到的是所有长度为$\lfloor\frac{n+1}{2}\rfloor$且包括这个元素的区间中价值和最小的区间.

为什么呢?

因为Bob一定可以控制Alice只能拿这个区间.

假设$n$是偶数,我们将整个环去掉这段区间,那么完全对称着去取就行了.

奇数的情况也是类似.

于是利用单调队列处理出所有起点的答案,再取最大值就行了.

代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 500010
int a[N<<1],sum[N<<1],q[N<<1],w[N<<1],fr,ta;
 
inline int getc(){
    static const int L=1<<15;
    static char buf[L],*S=buf,*T=buf;
    if(S==T){
        T=(S=buf)+fread(buf,1,L,stdin);
        if(S==T)
            return EOF;
    }
    return*S++;
}
inline int getint(){
    int c;
    while(!isdigit(c=getc()));
    int x=c-'0';
    while(isdigit(c=getc()))
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
 
int ans[N];
inline void mini(int&x,int y){
    if(x>y)
        x=y;
}
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    int n=getint(),m=(n+1)>>1,i,j;
    for(i=1;i<=n;++i)
        a[i]=a[n+i]=getint();
    for(i=1;i<=(n<<1);++i)
        sum[i]=sum[i-1]+a[i];
    for(i=1;i<=2*n-m+1;++i)
        w[i]=sum[i+m-1]-sum[i-1];
    memset(ans,0x3f,sizeof ans);
    for(i=1;i<=2*n;++i){
        if(i<=2*n-m+1){
            while(fr!=ta&&w[i]<w[q[ta-1]])
                --ta;
            q[ta++]=i;
        }
        while(fr!=ta&&q[fr]<i-m+1)
            ++fr;
        if(fr!=ta)
            mini(ans[i>n?i-n:i],w[q[fr]]);
    }
    int re=0;
    for(i=1;i<=n;++i)
        re=max(re,ans[i]);
    cout<<re<<endl;
    return 0;
}