UVA815 洪水！

紫书第四章习题

方法： 刚入门，一开始看没什么思路。。。
（借鉴大佬的思路）采用二分法，把输入进来的数据存到一维数组里，排序后再采用二分法。

具体思路是：二分一次，判断总水量能否淹没mid值之下的所有网格，如果能，则把区间往大了调（记得记录下来此刻的数据），如果不能，就往小了调。

PS：
1. 此题看了大佬的题解才知道每组数据后还需要多一个换行。。。
2. 只看了思路，结果因为自身编码水平不够，以为案例过了就能AC，导致我两个小时WA了8次。。。中途还出去到家乡的高速路上怀疑了一会儿人生（一度感觉自己是不是不适合编程。。。）

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
int s[maxn],vol;
long long sum;
bool guanshui(int mid){	//灌水 判断能不能灌mid前的网格
	sum=0;
	for(int x=1;x<mid;x++){
		sum+=(s[mid]-s[x])*10*10;
	}
	if(vol>sum) return 1;
	else return 0;
}

int main(){
	int m,n,count=0;
	double h,p;
	while(cin>>n>>m&&(n||m)){
//		if(count) cout<<endl;
		memset(s,0,sizeof(s));
		int tot=n*m,res;
		for(int i=1;i<=tot;i++){
			cin>>s[i];
		}
		cin>>vol;
		sort(s+1,s+tot+1);
//		for(int i=1;i<=tot;i++) cout<<s[i]<<endl;
		int l=0,r=tot,mid,ansp;
		while(l<=r){
			mid=(l+r)>>1;
			if(guanshui(mid)){
				ansp=mid;
				l=mid+1;
				res=sum;
			}
			else{
				r=mid-1;
			}
		}
//		cout<<mid<<endl;
		h=1.0*s[ansp]+1.0*(vol-res)/(10*10*ansp);
		p=100.0*ansp/tot;
		cout<<"Region "<<++count<<endl;
		printf("Water level is %.2lf meters.\n",h);
		printf("%.2lf percent of the region is under water.\n",p);
		cout<<endl;
	}
	return 0;
}