UVa 815 - Flooded!

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

中文網址

給你每一格的高度，水會從低的開始積。

Solution

花了一些時間才理解題目…

因為每格高度不同，所以水要先從低的格子開始積，一層一層往上看，向上原先那格自然上面也是水，直到又淹過了某一格。

寫成公式:

每塊土地面積 10x10
V = 水的體積
h = 水的高度
H[i] = 每一格地面的高度
i = 水能蓋過的最後一格，$H[i+1] > h$

$V = \left[ (h - H[0]) + (h - H[1]) + \cdots + (h - H[i]) \right] \times 10^2$

找出 i 後，就可以推出 h 了。再計算有幾格被淹的百分比時要小心精度問題。

Code

UVa 815

#include<cstdio>
#include<algorithm>
#include<climits>
using namespace std;

int main()
{
    int n, m, H[900], Case = 1;
    while (scanf("%d%d", &n, &m) && n)
    {
        int i;
        n *= m;
        for (i = 0; i < n; i++)
            scanf("%d", &H[i]);

        double h, sum = 0, V;
        scanf("%lf", &V);
        sort(H, H + n);

        H[n] = INT_MAX;
        
        //V = [ (h - H[0]) + (h - H[1]) + ... + (h - H[i]) ] * 10^2
        V /= 100;
        for (i = 0; i < n; i++)
        {
            sum += H[i];
            h = (V + sum) / (i + 1);
            if (h < H[i + 1])
                break;
        }

        printf("Region %d\n", Case++);
        printf("Water level is %.2lf meters.\n", h);
        printf("%.2lf percent of the region is under water.\n\n", (double)100 * (i + 1) / n);
    }

    return 0;
}