【题解】洪水

题目描述

干旱使得Farmer John农场上的草死了很多。所以他跳一种非洲部落舞蹈来求雨。制雨者知道他想求多少雨。不幸的是,制雨者太热情了,农场面临着洪水的威胁。帮助Farmer John找到水的高度,他可以把他的奶牛移到安全的地方。
农场是由M×N(1≤M≤400,1≤N≤400)的一个个一米边长的正方形方格组成的。每格有一个值为整数的海拔高度(1≤海拔高度≤10000)。给出一个M×N的表格和降水量V(1≤V≤1000000000)。
水总是先流到最低的方格,不管该方格在哪儿。
降水量总是整数。你必须算出水上升的高度,水面和海平面(海拔高度为0)之间的陆地的量(可能为0)。陆地高度和水面相同时看成被淹没,高出部分不会被水淹没。

输入输出格式

输入格式:

第一行,三个整数:M,N,V;
接下来是一个M×N的表格(整数)。

输出格式:

一行,两个整数,水上升的高度,水面和海平面之间的陆地的量。

输入输出样例

输入样例:

4 5 33
2 2 2 2 2
1 3 4 3 2
2 3 5 3 2
2 4 1 1 2

输出样例:

4 43
这道题很简单,但暴力会超时,所以可以改二分答案
先二分海平面的高度,再遍历农场,如果这个格子的海拔小于海平面,降水量-(海面高度-海拔)
如果水量小于0,往小的找;如果水量大于0,往大的找;如果水量等于0,输出
程序如下:

#include<iostream>
#include<cstdio>
using namespace std;
int line,list,ans;
long long v;
int farm[405][405],ans2;
int main()
{
	scanf("%d%d%d",&line,&list,&v);
	int maxx=-1;
	for(register int i=1;i<=line;++i)
	{
		for(register int j=1;j<=list;++j)
		{
			scanf("%d",&farm[i][j]);
			maxx=max(maxx,farm[i][j]);
		}
	}
	int left=1,right=maxx+2,mid;
	while(left<=right)
	{
		int temp=v;
		ans2=0;
		mid=(left+right)/2;
		for(register int i=1;i<=line;++i)
		{
			for(register int j=1;j<=list;++j)
			{
				if(farm[i][j]<mid) temp-=mid-farm[i][j];
				if(farm[i][j]<=mid) ans2+=farm[i][j];
			}
		}
		if(temp>0) left=mid+1;
		if(temp<0) right=mid-1;
		if(temp==0)
		{
			printf("%d %d",mid,ans2);
			break;
		}
	}
}
原文地址:https://www.cnblogs.com/2021-yanghaoran/p/10917584.html