当前位置: 代码迷 >> 综合 >> Uva815 Flooded
  详细解决方案

Uva815 Flooded

热度:69   发布时间:2023-12-05 13:32:48.0

原题:

本题有多种解法,偏向思维。最主要的是精度问题。

分析:对输入数据进行排序,水会先囤积在低海拔地区,低海拔区域存满后才开始浸入高海拔地区。 所以从海拔最低的地区开始更新最终海拔高度和实时剩余水量,当剩余水量严格大于0时更新淹没区域数量。通过淹没区域面积计算海拔高度。

代码:

#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#define EPS 1e-7
using namespace std;
int main(void)
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,m,kase=1;const long long single_S=100;while(cin>>n>>m&&n*m){vector<int> region(n*m);for(int i=0;i<n*m;i++){cin>>region[i];}sort(region.begin(),region.end(),less<int>());double altitude=region[0],rainfall;int sum=1;cin>>rainfall;rainfall/=single_S;for(int i=0;i<n*m;i++){if(i==n*m-1){altitude+=(1.0*rainfall/sum);}else{if(rainfall-sum*(region[i+1]-region[i])>EPS){rainfall-=(sum*(region[i+1]-region[i]));altitude=region[i+1];sum++;}else{altitude+=(1.0*rainfall/sum);break;}}}double percentage=100.0*sum/(n*m);cout<<"Region "<<kase++<<endl;cout<<"Water level is "<<setprecision(2)<<fixed<<altitude+EPS<<" meters."<<endl;cout<<setprecision(2)<<fixed<<percentage+EPS<<" percent of the region is under water."<<endl<<endl;}return 0;
}