243
技术社区[云栖]
POJ 1877 Flooded!
题目：将一个区域分成m*n个方块，每个方块有有一个海拔（可正可负）。求当给区域注入指定容量的水时，水面的海拔是多少，以及被水淹没的方块占总方块数的百分比。每个方块的面积为100m^2，水的容量单位为立方米。
我看到网上有一些解题报告写的都很复杂，其实没有那么复杂，细心看下面的代码应该很容易就看懂了。
思路是很简单的：由于是注水，水会先填满海拔低的方块，所以将方块按海拔从低到高排序。特别注意的就是现在的底面积是不断增加的。
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include <algorithm>
using namespace std;
int elevation[905]; //每个地区的海拔高度
int water; //最后注入的水，单位是立方米
const int MAXN=9999;//哨兵
double result,percentage; //最后的海拔高度和百分比
void testPrint(int Num)
{
for(int i=0;i<Num;i++)
printf("%d ",elevation[i]);
printf("\n");
}
int main()
{
//freopen("in.txt","r",stdin);
//10-meter squares 就是100平方米
int m,n; //m,n都不会超过30
int count=0;
int i;
int intercept; //高度差
int nowArea;//现在的底面积
while(scanf("%d%d",&m,&n))
{
if(m==0 && n==0)
break;
count++;
int regionNum=n*m;//看似一个二维数组，实际上就是一个一位数组
for(i=0;i<regionNum;i++)
scanf("%d",&elevation[i]);
elevation[i]=MAXN; //哨兵
scanf("%d",&water);
//排序
sort(elevation,elevation+regionNum); //ok
//testPrint(regionNum);
//先尝试从最少水的那个地方开始灌水
//高度就是他和下一个地区的高度差
for(i=0;i<regionNum;i++)
{
//如果水灌倒最后一个台阶，那就是都被淹了
intercept=elevation[i+1]-elevation[i];
nowArea=100*(i+1);
if (water>intercept*nowArea)
{
//放不下
water-=intercept*nowArea;
continue;
}
else
{
//剩下的水可以放得下
result=(double)water/(double)nowArea+elevation[i];
percentage=(double)((i+1)*100)/(double)regionNum;
break;
}
}
printf("Region %d\n",count);
printf("Water level is %.2lf meters.\n",result);
printf("%.2lf percent of the region is under water.\n\n",percentage);
}
return 0;
}
最后更新：2017-04-03 05:39:27