solution
显然答案具有单调性,如果答案为c。而对于任意一个,我们都可以在(c+1)~a的这些天里,让生长1的那个植株减1.
所以我们考虑二分答案,如果我们二分了一个答案x,我们可以先让那些水稻按照规则生长x天,最后再进行最多x次操作使他们高度相同即可。
那么现在问题就变为了,已经知道所有水稻高度,最少操作多少次使得所有水稻高度相同,显然最终高度肯定是现有水道中的一个,所以先排个序,然后枚举一下最终高度,计算一下操作次数即可。
复杂度
code
/* * @Author: wxyww * @Date: 2020-05-08 19:23:58 * @Last Modified time: 2020-05-08 19:50:01 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 100010; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } ll sum[N],n,a[N],b[N]; bool check(ll x) { ll t = x % n,k = x / n; for(int i = 1;i <= n;++i) b[i] = a[i] + k + (i <= t); sort(b + 1,b + n + 1); for(int i = n;i >= 1;--i) sum[i] = sum[i + 1] + b[i]; ll s = 0,ret = 1e18; for(int i = 1;i < n;++i) { ret = min(ret,(i - 1) * b[i] - s + sum[i + 1] - b[i] * (n - i)); s += b[i]; } return ret <= x; } int main() { n = read(); for(int i = 1;i <= n;++i) a[i] = read(); ll l = 1,r = 1e15; ll ans = 0; while(l <= r) { ll mid = (l + r) >> 1; if(check(mid)) ans = mid,r = mid - 1; else l = mid + 1; } cout<<ans; return 0; }