Skip to content

14025: 【原4025】洪水来袭

题目

题目描述

author: 肖云轩 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4025

Description

一场热带飓风席卷了圣安东尼奥城,百年不遇的强降水导致洪水爆发。Oven家的农场受此影响该地形成了星罗棋布的积水。
Oven家农场处于盆地,为一片长度为M,宽度为N的长方形网格区域,四周视作无限高的侧壁,每个网格位置(a,b)的海拔高度由一个M*N的矩阵表示,每个网格的面积视为1,农场地表的积水总体积为V。
由于这里的地层透水性很好,所以各片积水视作连通器,即各地的水平面海拔高度一致,低于水平面的网格必有水。
请帮助Oven计算出水平面的海拔高度,以及被淹没的地区(海拔高度严格小于水平面)的面积占总面积的百分比。(均保留两位小数)

Input Format

第一行,两个空格隔开的整数M,N。 (1 <= M,N <= 500)
第2 ~ M+1行输出一个M*N的矩阵。 (0 <= 高度 <= 1e8)
最后一行,整数V表示积水的体积。(0 <= V <= 1e12)

Output Format

第一行一个两位小数,水平面海拔高度。
第二行一个两位小数,被淹区域面积占总面积百分比。

Sample Input

3 3 
25 37 45 
51 12 34 
94 83 27 
100

Sample Output

46.67
66.67

Sample Input

2 2 
1 4 
4 10 
3

Sample Output

4.00
25.00

数据范围

对于60%的数据 (1 <= M,N <= 10)  
对于40%的数据 (10 < M,N <= 500)

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/23.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

using ll=long long;

int main() {
    int table[500 * 500 + 5];
    int M, N;
    cin >> M >> N;
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            scanf("%d", table + i * N + j);
        }
    }
    sort(table, table + M * N);
    int n = 0;
    while (n != M * N - 1 && table[n] == table[n + 1]) ++n;

    ll water;
    cin >> water;

    double height;
    double area;
    while (n != M * N - 1) {
        ll tmp = (table[n + 1] - table[n]) * (n + 1);
        if (water <= tmp) {
            height = table[n] + water / (n + 1.0);
            area = (n + 1.0) / (M * N) * 100.0;
            break;
        } else {
            water -= tmp;
            ++n;
            while (n != M * N - 1 && table[n] == table[n + 1]) ++n;
        }
    }
    if (n == M * N - 1) {
        height = table[n] + water / (n + 1.0);
        area = 100.0;
    }
    printf("%.2lf\n%.2lf\n", height, area);
    return 0;
}

FineArtz's solution

/* 洪水来袭 */
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;

//const long long INF = 2000000000000;

int main(){
    int m, n;
    cin >> m >> n;
    int a[250005] = {0};
    int sub[250005] = {0};
    for (int i = 1; i <= m * n; ++i)
        cin >> a[i];
    long long v;
    cin >> v;
    sort(a + 1, a + m * n + 1);
    if (v == 0){
        cout << setiosflags(ios::fixed) << setprecision(2) << double(a[1]) << endl;
        cout << "0.00" << endl;
        return 0;
    }
    double SeaLevel = 0.0;
    int cnt = 0;
    if (m <= 10 && n <= 10){
    /*for (int i = 1; i <= m * n; ++i)
        cout << a[i] << ' ';
    cout << endl;*/
        sub[1] = 0;
        for (int i = 2; i <= m * n; ++i)
            sub[i] = (a[i] - a[i - 1]) * (i - 1) + sub[i - 1];
    /*for (int i = 1; i <= m * n; ++i)
        cout << sub[i] << endl;*/
        cnt = 1;
        for (; cnt <= m * n; ++cnt)
            if (v <= sub[cnt]) break;
        --cnt;
        v -= sub[cnt];
        SeaLevel = a[cnt] + v * 1.0 / cnt;
    //cout << cnt << endl;
    }
    else {
        for (int i = 1; i <= m * n - 1; ++i)
            sub[i] = a[i + 1] - a[i];
        sub[m * n] = -1;
        cnt = 1;
        SeaLevel = a[1];
        while (1){
            if (v != 0 && cnt < m * n && v >= cnt * sub[cnt]){
                v -= cnt * sub[cnt];
                SeaLevel = a[++cnt];
            }
            else if (cnt >= m * n){
                cnt = m * n;
                SeaLevel += v * 1.0 / cnt;
                break;
            }
            else{
                SeaLevel += v * 1.0 / cnt;
                if (v == 0) --cnt;
                break;
            }
        }
    }
    cout << setiosflags(ios::fixed) << setprecision(2) << SeaLevel << endl
                                                       << cnt * 100.0 / (m * n) << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

constexpr int inf = 1000000009;
constexpr double jd = 1e-4;

int height[509][509] = { 0 };

int main() {
    int M, N;
    cin >> M >> N;

    int minh = inf, maxh = 0;

    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            scanf("%d", &height[i][j]);
            if (height[i][j] < minh)
                minh = height[i][j];
            if (height[i][j] > maxh)
                maxh = height[i][j];
        }
    }
    double V;
    cin >> V;

    double left = minh, right = 1e10, mid;
    int cnt = 0;
    while (right - left > jd) {
        mid = (left + right) / 2;
        cnt = 0;
        double v = 0;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (height[i][j] + jd < mid) {
                    ++cnt;
                    v += (mid - height[i][j]);
                }
            }
        }
        if (v < V) {
            left = (left + right) / 2;
        }
        else if (v == V)
            break;
        else {
            right = (left + right) / 2;
        }
    }

    printf("%.2f\n%.2f", mid, double(cnt) / double(M * N) * 100);

    return 0;
}

q4x3's solution

/**
 * 模拟
 * 排序后判断水淹到了哪里(扫描)
 * 注意处理全淹了的情况
 **/
#include <iostream>
#include <iomanip>

using namespace std;
double h[250233], H, per, earth, V;
int m, n;

template <typename T>
void merge(int lo, int mi, int hi, T* a)
{
    T* A = a + lo;
    int lb = mi - lo;
    T* B = new T[lb];
    T* BB = B;
    for(int i = 0;i < lb;++ i)
        B[i] = A[i];
    int lc = hi - mi;
    T* C = a + mi;
    int cnt = 0;
    while(1) {
        if ((lb == 0) && (lc == 0)) break;
        if (lb == 0) {
            A[cnt] = C[0];
            ++ cnt; ++ C; -- lc;
        }
        else if (lc == 0) {
            A[cnt] = B[0];
            ++ cnt; ++ B; --lb;
        }
        else {
            if(B[0] < C[0]) {
                A[cnt] = B[0];
                ++ cnt; ++ B; -- lb;
            }
            else {
                A[cnt] = C[0];
                ++ cnt; ++ C; -- lc;
            }
        }
    }
    delete []BB;
}

template <typename T>
void mergeSort(int lo, int hi, T* A)
{
    if(hi - lo < 2) return;
    int mi = (lo + hi) / 2;
    mergeSort(lo, mi, A); mergeSort(mi, hi, A);
    merge(lo, mi, hi, A);
}

int main()
{
    cin >> m >> n;
    for(int i = 0;i < m * n;++ i) cin >> h[i];
    cin >> V;
    mergeSort(0, m * n, h);
    per = m * n;
    for(int i = 0;i < m * n;++ i) {
        earth += h[i];
        H = h[i + 1] * (i + 1) - earth;
        if(H >= V) {per = i + 1; break;}
    }
    H = (V + earth) / per;
    per = 100 * per / (m * n);
    cout << fixed << setprecision(2) << H << endl << per << endl;
    return 0;
}

skyzh's solution

#include <iostream>
using namespace std;

int MAP[500][500];
int M, N;
double V;

int main() {
    cin >> M >> N;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            cin >> MAP[i][j];
        }
    }
    cin >> V;
    double L = 0, R = 1e18 + 1, H;
    int P = 0;
    double CV = 0;
    while (L + 1e-3 <= R) {
        H = (L + R) / 2;
        CV = 0;
        P = 0;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if ((double) MAP[i][j] < H) {
                    CV = CV + H - MAP[i][j];
                    ++P;
                }
            }
        }
        if (CV > V) R = H;
        else L = H;
    }
    printf("%.2lf\n%.2lf\n", H, (double) P / (M * N) * 100.0);
    return 0;
}

victrid's solution

#include <iomanip>
#include <iostream>
using namespace std;
int* MergeSort(int* list, int listSize) {
    if (listSize == 1)
        return list;
    if (listSize == 2) {
        if (list[0] > list[1]) {
            int temp = list[0];
            list[0]  = list[1];
            list[1]  = temp;
            return list;
        }
        return list;
    }
    int* tmplist = new int[listSize];
    int* llst    = MergeSort(list, listSize / 2);
    int* rlst    = MergeSort(list + listSize / 2, listSize - listSize / 2);
    int lct = 0, rct = 0;
    while (lct + rct != listSize) {
        if ((llst[lct] <= rlst[rct] && lct < listSize / 2) || rct >= listSize - listSize / 2) {
            tmplist[lct + rct] = llst[lct];
            lct++;
        } else {
            tmplist[lct + rct] = rlst[rct];
            rct++;
        }
    }
    for (int i = 0; i < listSize; i++) {
        list[i] = tmplist[i];
    }
    return list;
}

int main() {
    int n, m;
    cin >> n >> m;
    int size        = n * m;
    int* hgt        = new int[size];
    long long* hgt2 = new long long[size];
    for (int i = 0; i < size; i++) {
        cin >> hgt[i];
    }
    long long vol, existvol = 0;
    double ht = 0;
    cin >> vol;
    MergeSort(hgt, size); //from small to big
    hgt2[0] = 0;
    for (int i = 1; i < size; i++) {
        hgt2[i] = (hgt[i] - hgt[i - 1]) * i;
    }
    int hg = 0;
loop:
    existvol += hgt2[hg];
    if (existvol == vol) {
        ht = hgt[hg];
        goto ans;
    }
    if (existvol > vol) {
        ht = hgt[hg];
        ht -= (double)(existvol - vol) / (double)hg;
        goto ans;
    }
    hg++;
    if (hg == size) {
        ht = hgt[size - 1];
        ht += (double)(vol - existvol) / (double)size;
        goto ans;
    }
    goto loop;
ans:
    cout << setiosflags(ios::fixed) << setprecision(2) << ht << endl
         << (double)hg / (double)size * 100.0;
    return 0;
}