题解 CF671B 【Robin Hood】
拿到题目不着急，抽象成一个数学问题后，看看到底问了什么，要求什么：
题意很清晰，一个序列操作 K 次，每次最大值 -1 后最小值 +1 ，求最终的 最大值-最小值 。
这种区间最大最小值还带修改的问题当然自然的想到线段树啦！
然后发现 k ≤ 1e9
。。。。。。
我们学校的一名大佬说过：
处理一个1e9的整数当然是二分啊！
于是我们想想这道题怎么二分！
首先想想二分什么：
既然答案是 Max - Min ，你总不能直接二分这个答案吧。
所以考虑让这个东西最小，只要让 Max 最小而 Min 最大就好了。
所以我们分别二分这两个值，由于道理是相同的，就只讲 Max 的部分了：
经过 K 轮劫富济贫后，剩下的人最多的钱数为 Max ，那么很明显：
1，初始钱数不大于 Max 的人都不会被劫
2，初始钱数大于 Max 的人都会被劫 A[i] - Max 次
所以只要 O(N) 扫一遍看看达成当前的 Max 值的话，K 天够不够。
边界处理要略小心，因为最大值显然不会低于平均值，不会多于最富的人的钱，所以 L = Num / N + ( Num % N != 0 ) , R = Max A
这个 L 的意思就是，整除的话就是平均值，否则就是平均值 +1 。
对于 Min 做一次一样的二分， L = 1 , R = Num / N 整不整除都没关系。
最后输出 Max - Min
那么这样做为什么是对的呢？
闭上眼睛，感性理解，回顾一下我们在做什么：
两遍二分，我们都是尽量让最小值最大，最大值最小。
那么这个主人公在干什么呢？
他每次抢最多的人的钱给最少的人，尽量减小最大值，增加最小值，所以和我们做的事情是一样的。
于是这个二分是对的。
#include <cstdio>
using namespace std ;
inline long long Max( long long A , long long B ) { return A > B ? A : B ; }
inline long long Readin() {
register long long K = 0 ;
register char C = getchar() ;
for( ; C < '0' or C > '9' ; C = getchar() ) ;
for( ; C <= '9' and C >= '0' ; C = getchar() )
K = ( K << 1 ) + ( K << 3 ) + C - '0' ;
return K ;
}
long long N , K ;
long long A[500005] ;
long long Sum ;
long long Arv ;
inline bool Check1( long long Num ) {
long long Ans1 = 0 ;
for(register long long i = 1 ; i <= N ; i++ )
Ans1 += Max( 0 , Num - A[i] ) ;
return Ans1 <= K ;
}
inline bool Check2( long long Num ) {
long long Ans2 = 0 ;
for(register long long i = 1 ; i <= N ; i++ )
Ans2 += Max( 0 , A[i] - Num ) ;
return Ans2 <= K ;
}
long long L , R , Mid ;
long long Maxx , Minn ;
int main() {
N = Readin() ;
K = Readin() ;
for(register long long i = 1 ; i <= N ; i++ ) {
Maxx = Max( Maxx , A[i] = Readin() ) ;
Sum += A[i] ;
}
Arv = Sum / N ;
Mid = ( L = 1 ) + ( R = Arv ) >> 1 ;
for( ; L < R ; Mid = L + R + 1 >> 1 )
Check1( Mid ) ? L = Mid : R = Mid - 1 ;
Minn = L ;
Mid = ( L = Arv + ( Sum % N != 0 ) ) + ( R = Maxx ) >> 1 ;
for( ; L < R ; Mid = L + R >> 1 )
Check2( Mid ) ? R = Mid : L = Mid + 1 ;
Maxx = L ;
return not printf( "%lld\n" , Maxx - Minn ) ;
} 二分真是个好东西。