poj 1877

问题：有一块由N*M个正方形构成的地形，每块面积是100平方米，每一块都有自己的海拔。假定雨水不会流出边界，不会渗入地下，问当降雨量为v时，会有百分之多少被雨水覆盖。

解题思路：

 
由于题目中特别声明水无论如何都会流到当前水面最低的地方，使得问题一下子简化了。很容易想到以下贪心算法：
1）  把每个格子的高度排序；
2）  以低格子到高格子的顺序填水，把水均匀的铺在当前的水面上，并不断更新当前水面面积，和剩余水量；
3）  若剩余水量为0，输出当前水面高度和水面覆盖率。
 
注意几个问题：
1、  水面每达到一个格子的高度，水面的面积也要随之扩大；
2、  高度有负值，水面的初始高度是最低格子的高度而不是0；
3、  考虑好若干个格子高度相等的情况；
4、  每个格子的面积是100；
5、  没有水时，覆盖率为0；
6、  水若刚好达到一个格子的高度，此格子不算被水覆盖；
7、  水面达到最高格子后，要把剩下的水均匀的铺在整个区域上；
8、  注意浮点数的计算误差，因为这个原因大家在POJ上都没有通过此题:-<

代码如下：

#include <iostream>
using namespace std;
int h[1000];

int cmp(const void *a,const void *b)
{
	return *((int *)a)-*((int *)b);
}


int main()
{
	int m,n,t,nn;
	double hw,x;
	int i;
	t=0;
	while (true)
	{
		cin>>m>>n;
		if(0==n&&0==m)
			break;
		t++;
		nn=m*n;
		for (i=0;i<nn;i++)
			cin>>h[i];
		cin>>x;
		qsort(h,nn,sizeof(int),cmp);
		i=0;
		hw=h[0];
		if(x>0)
		{
			for (i=1;i<nn;i++)
			{
				while (i<nn&&h[i]==h[i-1])
				{
					i++;
				}
				if (i==nn||x<100*i*(h[i]-h[i-1]))
					break;
				x-=(h[i]-h[i-1])*i*100;
			}
			hw=h[i-1];
		}
		if(x>0)
		{
			while (i<nn&&h[i]==h[i-1])
			{
				i++;
			}
			hw+=x/i/100;
		}
		printf("Regin %d\n",t);
		printf("Water level is %.2f metres.\n",hw);
		printf("%.2f percent of the region is under water.\n\n ",i*100/double(nn));
	}
	return 0;

}