HDU - 6383 p1m2 （二分）

原题链接：

中文题，题意大概就是给定一个非负整数数组，对其中的某两个数进行+1 与-2，直到数组中最大值-最小值<=1

这题一开始一点思路都没有，也是看了网上的代码，理解了下

思路：搜索出一个mid值使得所有数据与mid的差的总和最小且总和>0

解析：这个mid值的差其实就是该数据需要提升或降低的次数，因为是+1和-2，所以-2的次数肯定也要/2

如下：

for(int i=0;i<n;i++){
	if(a[i]>mid)sum+=(a[i]-mid)/2;
	else sum+=a[i]-mid;
}

也可以理解为一种能力，大于mid的有下降能力，小于mid的有上升能力

计算完sum后

如果sum>0，说明还有数据具有下降能力，将左边界提升，mid上调，

如果<0，说明还有数据具有上升能力，将右边界下降，mid下调

最后输出的r即为答案（原因在二分模板中有解释：）

具体代码：

#include<iostream>
#include<cmath>
#define MAX_N 300005
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int a[MAX_N];
int max(int i,int j){
	return i>j?i:j;
}
	
int min(int i,int j){
	return i<j?i:j;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,l=INF,r=-1,mid;
		ll sum=0;
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>a[i];
			l=min(l,a[i]);
			r=max(r,a[i]);
		}
//		cout<<l<<" "<<r<<endl;
		while(l<=r){
			sum=0;
			mid=(l+r)/2;
			for(int i=0;i<n;i++){
				if(a[i]>mid)sum+=(a[i]-mid)/2;
				else sum+=a[i]-mid;
			}
			if(sum>=0)l=mid+1;
			else r=mid-1;
//			cout<<l<<" "<<r<<endl;
		}
		cout<<r<<endl;
	}
}