牛客练习赛63 C题

牛客练习赛63 C题：牛牛的揠苗助长
比赛时的心路历程：如果直接暴力会超时（亲身试错），所以要寻求一个更快速的算法，最后想到是用二分算。
首先我们需要明白一个前提：如果说经过了x天后所有水稻都达到了相同高度，那么以后将能够持续保持相同高度，因为每天只有一块水稻自然生长，我们只需要使用魔法将它压回去就行了。
-->那么问题就可以变成：假设时间来到了mid天
1、如果这时可以达到相同高度，那么在mid天之前的某一天也可能达到了相同高度，这时我们就把右边界R=mid-1；
2、如果这时不能达到相同高度，那么只有可能在以后的某一天才能达到相同高度，因此把左边界L=mid+1；
-->最后的问题就是如何判断在mid天能否达到相同高度呢？
这里直接借用官方题解的图：

这里需要说明一下，将此时的水稻高度升序排序，然后将最中间的那一块水稻标记下来（图中的为i=4），其他的水稻都要向它的高度看齐，阴影部分的面积就是需要的最小天数（这个结论可以在官方题解中看到，在这里就不详细说明了）而阴影部分的面积s=ia[i]-getsum(1,i)+getsum(i+1,n)-(n-i)a[i]
我们再把s和mid作比较，如果s<=mid,说明在mid天或mid天以前能够达到相同高度；如果s>mid,说明在mid天还不能达到相同高度。
到此所有的问题都已经解决了,下面贴代码

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int n;
#define N 1e14
long long a[100005],b[100005];//a为水稻高度数组，b为辅助数组，因为每次判断都要重新更改水稻高度 
long long ans=0;
long long L=1;//初始值左边界 
long long R=N;//初始值右边界设为最大矩形面积，也就是最大的天数 

long long getsum(int x,int y){//求区间（x，y）和 
    long long z=0;
    for(int i=x;i<=y;i++){
        z=z+b[i];
    }
    return z;
}

bool OK(long long mid){//判断mid天能不能达成条件 
    long long x=0;
    for(int i=1;i<=n;i++){
        b[i]=a[i]+mid/n+(mid%n>=i); //计算经过mid天后，自然生长情况下各个水稻的高度 
    }
    sort(b+1,b+1+n);//升序排列 
    x=(1+n)/2;
    long long s=b[x]*x-getsum(1,x)+getsum(x+1,n)-b[x]*(n-x);//计算阴影部分的面积 
    if(s<=mid) return true;
    else return false;
}


int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    while(L<=R){//二分 
            long long mid=L+R>>1;
            if(OK(mid)){
                ans=mid;
                R=mid-1;
            }
            else L=mid+1;
        }
    cout<<ans;
}