管道C语言（蓝桥杯题库，暴力解决）_acm比赛中管道问题

问题描述

有一根长度为 \text{len}len 的横向的管道，该管道按照单位长度分为 \text{len}len 段，每一段的中央有一个可开关的阀门和一个检测水流的传感器。

一开始管道是空的，位于 L_iLi​ 的阀门会在 S_iSi​ 时刻打开，并不断让水流入管道。

对于位于 L_iLi​ 的阀门，它流入的水在 T_iTi​ (T_i \geq S_iTi​≥Si​) 时刻会使得从第 L_i - (T_i - S_i)Li​−(Ti​−Si​) 段到第 L_i + (T_i - S_i)Li​+(Ti​−Si​) 段的传感器检测到水流。

求管道中每一段中间的传感器都检测到有水流的最早时间。

输入格式

输入的第一行包含两个整数 n,\text{len}n,len，用一个空格分隔，分别表示会打开的阀门数和管道长度。

接下来 nn 行每行包含两个整数 L_i,S_iLi​,Si​，用一个空格分隔，表示位于第 L_iLi​ 段管道中央的阀门会在 S_iSi​ 时刻打开。

输出格式

输出一行包含一个整数表示答案。

样例输入

3 10
1 1
6 5
10 2

样例输出：5

思路：这里采用的暴力求解，一个一个列时间，然后通过时间来看，当前时间管道的的水是否充满，如果充满了，就可以输出当前时间，可以用数组来记录，当一个管道充满水就让当前数组对应的值为1，没有水的为1，然后遍历整个数组，如果全为0的话，就说明全部充满了。

代码：

#include <stdio.h>
int main(){
	int m,n,j,i,t,x,y,zum=0;
	scanf("%d%d",&n,&m);//n个阀门   //m个管道
	long long int guandao[10000]={0},num[10000]={0},dp[10000]={0};
	for(i=0;i<n;i++){
		scanf("%d",&j);//输入第j个管道 
		num[j]=1;
		scanf("%d",&guandao[j]);//第j个管道第~~时刻有水 
	} 
	for(t=1;t<=1000;t++){//遍历时间 
		zum=0;
		for(j=1;j<=m;j++){//遍历每一个管道 
			if(num[j]==1){
				 if(guandao[j]<=t){//当管道放水时间小于等于时间的时候，才有水 
					int l=t-guandao[j];//这里是在求打开之后，水流了多少格 
					int s=j-l,p=j+l;
					if(j-l<=1){//防止数组溢出，当水流到管道尽头的时候，就要 
						s=1;   //改变循环范围 
					}
					if(p>=m){
						p=m;
					} 
					for(x=s;x<=p;x++){
						dp[x]=1;
					}
				}
			}
		}
		for(y=1;y<=m;y++){
			if(dp[y]!=1){//这里就是检测整个dp数组，如果有一个为1就说明没有充满 
				zum=1;//这个时候zum=1； 
			}
		}
		if(zum==0){//如果zum没有为一的时候，就说明dp都满足有水 
			printf("%d",t);//打印当前时间， 
			return 0;//结束函数 
		}
	}
	return 0;
}