UVa 815 Flooded!

浏览: 240 发布日期: 2018-01-01 分类: c

Flooded!

Time Limit: Unknown Memory Limit: Unknown
Total Submission(s): Unknown Accepted Submission(s): Unknown


https://uva.onlinejudge.org/i...

Accepted Code

#include "stdio.h"

#define MAX 1000

typedef struct {
    int level;     // 海拔
    int space;     // 底面积
    int flag;     // 土地标志
}LAND;

int main()
{
    int m, n;
    int region = 0;
    while (scanf("%d%d", &m, &n) != EOF)
    {
        if (m == 0 && n == 0)
            break;

        region += 1;
        // 输入土地海拔和雨水量
        LAND a[MAX];
        int t = m * n;
        for (int i = 0; i < t; i++) {
            scanf("%d", &a[i].level);
            a[i].space = 100;
            a[i].flag = 1;
        }
        int rain;
        scanf("%d", &rain);
        // 按海拔升序
        for (int i = 1; i < t; i++) {
            for (int k = 0; k < t - i; k++) {
                if (a[k].level > a[k + 1].level) {
                    LAND tmp = a[k];
                    a[k] = a[k + 1];
                    a[k + 1] = tmp;
                }
            }
        }
        // 把海拔相同的土地归并
        int i, k;
        for (i = 0; i < t - 1; i = k) {
            for (k = i + 1; a[i].level == a[k].level; k++) {
                a[i].space += a[k].space;
                a[k].flag = 0;
                a[i].flag += 1;
            }
        }
        // 把有效土地存到另一个数组
        LAND b[MAX];
        k = 0;
        for (i = 0; i < t; i++) {
            if (a[i].flag) {
                b[k++] = a[i];
            }
        }
        b[k].level = 0xFFFFFFF;     // 在末尾加个无限高的墙
        t = k + 1;
        // 模拟注水过程
        int cap = 0;
        double level = 0;
        for (i = 0; i < t - 1; i++) {
            cap = b[i].space * (b[i + 1].level - b[i].level);
            b[i + 1].space += b[i].space;
            rain -= cap;
            level = b[i + 1].level;
            if (rain <= 0) {
                rain += cap;
                level = b[i].level;
                level += 1.0 * rain / b[i].space;
                break;
            }
        }
        int count = 0;
        for (k = 0; k <= i; k++) {
            count += b[k].flag;
        }
        double area = 100.0 * count / (m * n);
        // 输出结果
        printf("Region %d\n", region);
        printf("Water level is %.2lf meters.\n", level);
        printf("%.2lf percent of the region is under water.\n\n", area);
    }
    return 0;
}

Notes

题意:
有一个m*n的网格,每个格子是边长为10米的正方形,网格四周是无限高的墙。输入每个格子的海拔高度,以及网格内雨水的总体积,输出水位的海拔高度以及有多少百分比的区域内有水(即高度严格小于水平面)。

思路:
将土地依照海拔升序排成一列,模拟注水过程即可。

//-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//
// 作者:龙威昊
// 完成时间:2017/12/31
//
//-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

返回顶部