学步园

  一道world final的水题。说起这道题还有个小故事，我在msra当 intern时的舍友，曾经去面google总部inern时候被问的一道题目和这道题目挺像的，只是从二维变成一维，后来一个同学提起，就顺便刷了下。

  最大的难点是理解题目，其实就是顺着题目的意思对每块地的海拔排个序后，一块地一块地的遍历过来就好，不过注意各种极端情况。

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int regionIndex=0;
	int n,m;
	double region[1000];
	double totalWaterCubic;
	double waterLevel;
	double floodedPercent;

	scanf("%d%d",&m,&n);

	while(n!=0 && m!=0)
	{
		regionIndex++;

		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
			{
				scanf("%lf",®ion[i*m+j]);
			}
		scanf("%lf",&totalWaterCubic);

		if(n==1&&m==1)
		{
			if(totalWaterCubic>0.0f)
			{
				waterLevel=totalWaterCubic/100.0f + region[0];
				floodedPercent=100.00f;
			}
			else
			{
				waterLevel=0.0f;
				floodedPercent=0.0f;
			}
		}

		else
		{
			if(totalWaterCubic==0.0f)
			{
				waterLevel=0.0f;
				floodedPercent=0.0f;
			}

			else
			{
				sort(region,region+n*m);

				double curFloodedCubic=0.0f;
				int curFloodedIndex=0;
				for(int i=1;i<n*m;i++)
				{
					//If square i is flooded, it need addedFloodedCubic cubic of water.
					double addedFloodedCubic=(region[i]-region[i-1])*i*100.0f;
					if(curFloodedCubic+addedFloodedCubic<totalWaterCubic)//the square is flooded
					{
						curFloodedCubic+=addedFloodedCubic;

						if(i==n*m-1)//All the squares are flooded.
						{
							double leftWaterCubic=totalWaterCubic-curFloodedCubic;
							waterLevel=leftWaterCubic/((i+1)*100.0f)+region[i];
							floodedPercent=100.00f;
							break;
						}
					}
					else//Those squares whose height are higher than square i-1 are no more flooded.
					{
						double leftWaterCubic= totalWaterCubic-curFloodedCubic;
						waterLevel=leftWaterCubic/(i*100.0f)+region[i-1];
						floodedPercent=(double)i/(double)(n*m)* 100.0f;
						break;
					}
				}
			}
		}

	    //Outpu the result
		printf("Region %d\n",regionIndex);
		printf("Water level is %.2lf meters.\n",waterLevel);
		printf("%.2lf percent of the region is under water.\n",floodedPercent);
		printf("\n");

		scanf("%d%d",&m,&n);
	}

	return 0;
}