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