题目

★实验任务

有一只小仓鼠身处在一个 N*M 迷宫之中，它现在想知道它最快能什么时候到达出口。

迷宫是由 ‘ . ’ ‘ # ’ 构成，’ . ’表示可以通行，‘#’表示墙壁，不能通行，现在小仓鼠在‘S’的位置上，问到出口’E’的最短时间是多少？

★数据输入

第一行两个整数 n,m(1<n,m<=1000)表示 n 行，m 列

接下来输入一个 n*m 的迷宫(只包含 ’ . ’ , ’ # ’, ’ S ’,’ E ’)

★数据输出

如果能到达则输出最短时间，否则输出-1。

样例1 输入：

6 3
-1 2 -6 5 -5 6

样例1输出：

6 4 6

样例2输出：

5 5
-1 -1 -1 -1 -1

样例2输出：

-1 1 1

解题思路：

使用前缀和方法然后进行区间查找

解题代码：

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int sum[100005];
int lef,righ;
int minsum=1000000;
int n,k,length=-1000000;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=a[i]+sum[i-1];
		if(sum[i]<minsum){
			minsum=sum[i];
			lef=i;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=i;j<=i+k;j++){
			if(j>n) break;
			if(i==j){
				if(sum[i]>length){
					lef=i;
					righ=j;
					length=sum[i];
				}
			}
			else if((sum[j]-sum[i])>length){
				lef=i+1;
				righ=j;
				length=sum[j]-sum[i];
			}
		}
	} 
	//cout<<sum[lef]<<endl<<sum[righ]<<endl;
	cout<<length<<" "<<lef<<" "<<righ;
	return 0;
}