使用枚举法会超时，如何减少时间复杂度。c++
已知有n项活动和每一项所需的时间，活动编号从1到n，每项活动在周六和周日各开展一次。 小明决定周六和周日分别参加编号连续的k项活动，而且不会重复参加同一种活动（即若在某一天选择参加了活动m，则在另一天不会再参加活动m）。 请帮忙找出周六和周日花费的总时间最少的选择。
输入
第一行为一个整数n和一个整数k，n代表有n项活动，k代表小明周六和周日每天参加的活动数量，n和k用空格隔开。
接下来的一行为n个整数，分别表示一项活动完成的时间，用空格隔开。
输出
输出为两个整数，表示周六和周日选择的起始活动编号。如果有多个方案，请输出周六起始活动编号较小的方案；如果仍有多个方案，请输出周日起始活动编号较小的方案。
例1输入：
5 2
6 1 8 2 1
例1输出：
1 4
解释：
根据“参加编号连续的k项活动”要求，可供小明选择的活动安排有：
方案一、周六参加编号1和2的k项活动，时长分别为6和1；周日参加编号3和4的k项活动，时长分别为8和2。
方案二、周六参加编号1和2的k项活动，时长分别为6和1；周日参加编号4和5的k项活动，时长分别为2和1。
方案三、周六参加编号2和3的k项活动，时长分别为1和8；周日参加编号4和5的k项活动，时长分别为2和1。
方案四、周六参加编号3和4的k项活动，时长分别为8和2；周日参加编号1和2的k项活动，时长分别为6和1。
方案五、周六参加编号4和5的k项活动，时长分别为2和1；周日参加编号1和2的k项活动，时长分别为6和1。
方案六、周六参加编号4和5的k项活动，时长分别为2和1；周日参加编号2和3的k项活动，时长分别为1和8。
在这6种活动安排方案中，总时间最少的是方案二和方案五， 根据题目要求，应选择周六起始活动编号较小的方案二，输出周六和周日的起始活动编号1和4。
```c++
#include ```
空间换时间的方法，用一个数组存放k项活动总时间，避免重复循环求和。
#include <iostream>
using namespace std;
int a[50000], s[50000]; //s[i] = a[i] + a[i+1] + ... + a[i+k]
int main() {
int n = 0, k = 0, i, j, t;
cin >> n >> k;
for (i = 0; i < n; i++)cin >> a[i];
for (t = 0, i = 0; i < k; i++)t += a[i];
//计算连续k项活动消耗时间
for (s[i - k] = t; i < n; i++) {
t = t - a[i - k] + a[i];
s[i - k+1] = t;
}
int min,r1=0,r2=0;
//给min赋int类型最大的数
for(i=0;i<sizeof(int)*8-1;i++){
min|=1<<i;
}
//枚举
for(i=0;i<n-2*k+1;i++){
for(j=i+k;j<n-k+1;j++){
if(s[i]+s[j]<min){
min=s[i]+s[j];
r1=i+1;
r2=j+1;
}
}
}
cout << r1 << " " << r2 << endl;
return 0;
}
该回答引用ChatGPT
实现代码
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n), s(n+1);
for (int i = 0; i < n; i++) {
cin >> a[i];
s[i+1] = s[i] + a[i];
}
int min_sum = 2e9, min_start = 0;
for (int i = 1; i <= n-k+1; i++) {
for (int j = i+k; j <= n-k+2; j++) {
int sum = s[i+k-1] - s[i-1] + s[j+k-1] - s[j-1];
if (sum < min_sum) {
min_sum = sum;
min_start = i;
}
}
}
cout << min_start << " " << min_start+k << endl;
return 0;
}