洛谷P1514 [NOIP 2010 提高组] 引水入城

洛谷题目传送门

题目背景

NOIP2010 提高组 T4

题目描述

在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个 $N$ 行 $M$ 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。

为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。

因此，只有与湖泊毗邻的第 $1$ 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。由于第 $N$ 行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。

输入格式

每行两个数，之间用一个空格隔开。输入的第一行是两个正整数 $N,M$，表示矩形的规模。接下来 $N$ 行，每行 $M$ 个正整数，依次代表每座城市的海拔高度。

输出格式

两行。如果能满足要求，输出的第一行是整数 $1$，第二行是一个整数，代表最少建造几个蓄水厂；如果不能满足要求，输出的第一行是整数 $0$，第二行是一个整数，代表有几座干旱区中的城市不可能建有水利设施。

输入输出样例 #1

输入 #1

2 5
9 1 5 4 3
8 7 6 1 2

输出 #1

1
1

输入输出样例 #2

输入 #2

3 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2

输出 #2

1
3

说明/提示

样例 1 说明

只需要在海拔为 $9$ 的那座城市中建造蓄水厂，即可满足要求。

样例 2 说明

上图中，在 $3 $ 个粗线框出的城市中建造蓄水厂，可以满足要求。以这 $3 $ 个蓄水厂为源头在干旱区中建造的输水站分别用 $3$ 种颜色标出。当然，建造方法可能不唯一。

数据范围

本题有 10 个测试数据，每个数据的范围如下表所示：

测试数据编号	能否满足要求	$N\le$	$M\le$
1	不能	$10$	$10$
2	不能	$100$	$100$
3	不能	$500$	$500$
4	能	$1$	$10$
5	能	$10$	$10$
6	能	$100$	$20$
7	能	$100$	$50$
8	能	$100$	$100$
9	能	$200$	$200$
10	能	$500$	$500$

对于所有 10 个数据，每座城市的海拔高度都不超过 $10^6$。

思路详解

我们发现，一条河流可以流到的干旱城市是固定的，考虑直接将他预处理出来。我们发现倘使一条河流对应一个连续区间，那我们直接贪心即可，但如果不呢？？？如果问题不能解决，那考虑如何解决掉问题。考虑如何证明一定是一条连续区间。

连续区间

对于无解的情况，我们肯定不需要讨论，因为我们可以直接标记。那对于有解的情况，如何证明每个河流对应的一定是一个连续区间的。考虑使用反证法，如下图：

假如$x$可以流到下端蓝线除了红点的城市，由于有解，则必有如下城市可以到达红点：

我们发现$x$，$y$的流径一定有交点，不然$y$不可能凭空到达红点。那么你$y$都可以走，则$x$肯定可以走到，那$x$流经地区一定是一个连续区间，那接下来就好办了。

大致思路

大致思路如下：

1. 我们先以每个河流为起点，深搜求解每个河流可以流经的区间。
2. 然后在检查干旱城市是否都可以被灌溉，如果不是统计有多少个，输出即可。
3. 如果都可以，则对应每个区间，我们以已有区间右边界的右边一个为起点，若新区间的的左端点小于等于起点，则取右端点的最大值为新的右边界。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m;
int a[N][N],vis[N][N];
struct node{int x,y;
}c[N][N];//c[i][j]为从(i,j)开始可以流到的区间
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
int jsq=0;
void dfs(int bx,int by){//深搜求解vis[bx][by]=1;for(int i=0;i<4;i++){auto [qx,qy]=(node){bx+dx[i],by+dy[i]};if(qx<1||qx>n||qy<1||qy>m||a[qx][qy]>=a[bx][by])continue;if(!vis[qx][qy]){//注意，访问过的点也可以更新他的值vis[qx][qy]=1;dfs(qx,qy);}c[bx][by].x=min(c[bx][by].x,c[qx][qy].x);c[bx][by].y=max(c[bx][by].y,c[qx][qy].y);}
}
int ans=0;
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)c[i][j].x=0x3f3f3f3f;}//赋初值for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];if(i==n)c[i][j]={j,j};//边界}}for(int i=1;i<=m;i++){//枚举并深搜if(!vis[1][i])dfs(1,i);}for(int i=1;i<=m;i++)if(!vis[n][i])ans++;//记录有多少个点流不到if(ans>0){//有城市流不到cout<<0<<'\n'<<ans;}else{cout<<1<<'\n';ans=0;int l=1,r=0;while(l<=m){//贪心for(int i=1;i<=m;i++){if(c[1][i].x<=l)r=max(r,c[1][i].y);}l=r+1;ans++;}cout<<ans;}return 0;
}