UVa 815 - Flooded!（快速排序）

发表于 分类于 ， Disqus：

输入水量和每个地点的高度，求有多少地方被淹了。

首先进行排序，水下部分的体积加到水里。然后依次判断，每淹没一个，就把那个的体积加到水里，一直到全部淹没或者无法淹没为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<iomanip>//当时居然用了这么奇怪的头文件。控制流式输出精度用的。
#include<algorithm>
#define EPS 1e-8
using namespace std;
int m,n,v,flood,cnt2;
double h,x,s,cnt1;
int main()
{
    int t=1;
    while(cin>>m>>n)
    {
        if(!m&&!n)
            break;
        int ld[m*n];
        cnt1=m*n;
        flood=v=0;
        h=x=0;
        for(int i=0;i<m*n;i++)
            cin>>ld[i];
        sort(ld,ld+m*n);//排序。
        cin>>flood;
        v+=flood+ld[0]*100;
        s=100;
        h=v/s+EPS;
        cnt2=1;
        for(int i=1;i<m*n;i++)
            if(h>ld[i])//循环判断能否淹没。
            {
                v+=ld[i]*100;
                s+=100;
                h=v/s+EPS;
                cnt2++;
            }
        cout<<"Region "<<t<<endl;
        cout<<"Water level is "<<setiosflags(ios::fixed)<<setprecision(2)<<h<<" meters."<<endl;//用printf比这个简单多了。
        cout<<setiosflags(ios::fixed)<<setprecision(2)<<100*cnt2/cnt1<<" percent of the region is under water."<<endl;
        cout<<endl;
        t++;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

相关文章