p1877.cpp

来自「大概POJ上50道比较难的题的代码」· C++ 代码 · 共 32 行

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 40;
int main(){
    int a[MAXN*MAXN],f[MAXN*MAXN];
    int r,c,N(0);
    double w;
    while(cin >> r >> c && (r || c)){
        int n(r*c);
        for(int i = 0;i < n;++i) scanf("%d",&a[i]);
        sort(a,a+n);
        f[0] = a[0];
        for(int i = 1;i < n;++i) f[i] = f[i-1] + a[i];
        cin >> w;
        w /= 100.0;
        int s(0),t(n-1),m;
        while(s <= t){
            m = s + t >> 1;
            if(m == n-1 || (w + f[m]) / (m+1) >= a[m])
                if(m == n-1 || (w + f[m+1]) / (m+2) <= a[m+1]){
                    printf("Region %d\n",++N);
                    printf("Water level is %.2lf meters.\n",(w + f[m]) / (m+1));
                    printf("%.2lf percent of the region is under water.\n",(m+1) * 100.0 / n);
                    break;
                }
                else s = m + 1;
            else t = m - 1;
        }
    }
}