CF363B Fence 题解

题意简述

给定一个长为 $n$ 的序列，要求截取一段长度为 $k$ 的连续子序列，使这段子序列的和最小。

解题思路

如果每次都去枚举这个数之后 $k$ 个数的和再进行比较，那么时间复杂度就会飙升到 $O(n^2)$。

数据要求 $1 \leqslant n \leqslant 1.5 \times 10^5$，肯定过不了。

所以可以想到用前缀和优化。

这里用一维数组前缀和，具体代码如下：

for(int i=1;i<=n;i++) scanf("%d",&sum[i]);
for(int i=1;i<=n;i++) sum[i]+=sum[i-1];

这里的 $sum$ 数组就表示前缀和。这里也用 $sum$ 数组来输入。

那么区间的和就可以表示为 $sum_{i+k-1} - sum_{i-1}$ 。

即 sum[i+k-1]-sum[i-1]。

如果这个区间和小于目前最小值 $minn$，那么将 $minn$ 更新。

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,k,sum[1000005],minn=INT_MAX,ans=INT_MIN;
int main() {
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&sum[i]);
	for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
	for(int i=1;i<=n-k+1;i++) {
		if(sum[i+k-1]-sum[i-1]<minn) {
			minn=sum[i+k-1]-sum[i-1];
			ans=i;
		}
	}
	if(k==n) printf("1");
	else printf("%d",ans);
	return 0;
}