# 14025: 【原4025】洪水来袭

### 题目描述

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

## Description

Oven家农场处于盆地，为一片长度为M,宽度为N的长方形网格区域，四周视作无限高的侧壁，每个网格位置(a,b)的海拔高度由一个M*N的矩阵表示，每个网格的面积视为1，农场地表的积水总体积为V。

## 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)

``````

## 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;
}
``````