Codeforces Round 703 (Div. 2)

A. Shifting Stacks

int a[N];
void solve(){
    int n=read(),ans=1;
    for(int i=1;i<=n;i++)a[i]=read();
    int rest=0,last=-1;
    for(int i=1;i<=n;i++){
        a[i]+=rest;
        rest=a[i]-last-1;
        last++;
        if(rest<0){
            ans=0;
            break;
        }
    }  
    puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

B. Eastern Exhibition

int x[N],y[N];
void solve(){
    int n=read();
    for(int i=1;i<=n;i++){
        x[i]=read(),y[i]=read();
    }
    if(n%2){
        cout<<1<<'\n';
        return ;
    }
    sort(x+1,x+1+n);sort(y+1,y+1+n);
    cout<<(x[n/2+1]-x[n/2]+1)*(y[n/2+1]-y[n/2]+1)<<'\n';
    
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

C1&&C2. Guessing the Greatest

这题很明显 需要通过第二大的值的位置来找最大值

先询问整体的第二大值 然后通过询问知道最大值在第二大值的哪一边

然后二分这一边即可

注意：询问的时候注意l,r不能相等 需要一些特判

int ask(int l,int r){
    cout<<"? "<<l<<" "<<r<<endl;
    return read(); 
}
void solve(){
    int n=read(),l=1,r=n;
    while(l<r){
        int secpoi=ask(l,r);
        int left=0;
        if(secpoi==n||(secpoi!=1&&secpoi==ask(1,secpoi)))left=1,r=secpoi-1;
        else l=secpoi+1;
        if(left==1){
            while(l+1<r){
                int mid=l+r>>1;
                if(ask(mid,secpoi)==secpoi) l=mid;
                else {
                    r=mid-1;
                }
            }
        }else {
            while(l+1<r){
                int mid=l+r>>1;
                if(ask(secpoi,mid)==secpoi) r=mid;
                else {
                    l=mid+1;
                }
            }
        }
        if(l+1==r){
            if(l==secpoi){l=r;
                break;}
            else if(r==secpoi){ r=l;
                break;}
        }
        if(l+1==r){
           int p=ask(l,r);
            if(l==p)l=r;
            else if(r==p) r=l;
        }
        
    }
    cout<<"! "<<l<<endl;
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

D. Max Median

明显的 答案具有二分性 所有选择二分答案

将mid小的值赋值为-1 比mid大的值赋值为1

然后求前缀和 和前缀最小值 如果前缀和减去前缀最小值大于0 说明是可行的

因为前缀最小值代表了前面有几个数小于mid 前缀和则是代表了有x个数大于等于mid 相减就去除了之前的数组造成的影响

int a[N],b[N],sum[N],minn[N],n,m;
bool check(int x) {
    for(int i=1;i<=n;i++)b[i]=(a[i]>=x?1:-1);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+b[i],minn[i]=min(minn[i-1],sum[i]);
    for(int i=m;i<=n;i++)if(sum[i]-minn[i-m]>0)return true;
    return false;
}
int bs2(int l, int r){ 
    while (l < r){
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}
void solve(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    cout<<bs2(1,n)<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}