UVA815

這道題主要學到的就是數據結構的組織，一些需要從小到大排列的東西，這些東西還有對應的東西。這個時候使用map可以解決

下面貼出代碼。其中所使用的思想，估計這個東西是沒法學的，這就只能是靈感

//這是什么吉爾題，題意都沒有說清楚，排水系統保證從最低的開始，而且四面都是高地
//我想要的數據結構是，從小到大把海拔排序，每個海拔對應=這個海拔的塊數，以及比這個海拔低的塊數
//最后計算的時候，可以很容易的計算出快要淹沒這個海拔時所需要的體積，海拔差*比這個海拔低的塊數
#include<cstdio>
#include<map>
using namespace std;struct square{int this_level;int lower_level;int cubic_meters;};map<int,square*>Map;int row,col;int cubic_meter;bool initial(){Map.clear();scanf("%d%d",&row,&col);if(!row){return false;}for(int i=0;i<row*col;i++){int level;scanf("%d",&level);if(!Map.count(level)){Map[level]=new square;Map[level]->this_level=1;}else{Map[level]->this_level++;}}scanf("%d",&cubic_meter);}void print_map(){for(map<int,square*>::iterator it=Map.begin();it!=Map.end();it++){printf("海拔%d的有  %d塊\n",it->first,it->second->this_level);printf("海拔比%d低的有  %d塊\n",it->first,it->second->lower_level);printf("恰好沒有淹沒這個海拔時的所需水的體積%d\n",it->second->cubic_meters);printf("\n");}}void compute(){if(cubic_meter==0){printf("Water level is %.2lf meters.\n",(double)Map.begin()->first);printf("0.00 percent of the region is under water.\n");return;}//先將恰好沒有埋沒每塊土地時，所需的水的體積計算出來int lower=0;for(map<int,square*>::iterator it=Map.begin();it!=Map.end();it++){it->second->lower_level=lower;lower=lower+it->second->this_level;}int lower_level=0,lower_cube=0;for(map<int,square*>::iterator it=Map.begin();it!=Map.end();it++){it->second->cubic_meters=it->second->lower_level*(it->first-lower_level)*100+lower_cube;lower_level=it->first;lower_cube=it->second->cubic_meters;}double water_level,percent;map<int,square*>::iterator it=Map.begin();for(;it!=Map.end();it++){if(it->second->cubic_meters>=cubic_meter){percent=(double)it->second->lower_level/(row*col);water_level=it->first-(it->second->cubic_meters-(double)cubic_meter)/(it->second->lower_level*100);printf("Water level is %.2lf meters.\n",water_level);printf("%.2lf percent of the region is under water.\n",percent*100);return;}}it--;water_level=((double)cubic_meter-it->second->cubic_meters)/(row*col*100)+it->first;printf("Water level is %.2lf meters.\n",water_level);printf("100.00 percent of the region is under water.\n");}int main(){
#ifdef localfreopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endifint kase=0;while(initial()){printf("Region %d\n",++kase);compute();printf("\n");// print_map();//compute();
     }return 0;}

?