关于#c++#的问题，请各位专家解答！

Question

使用枚举法会超时，如何减少时间复杂度。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 <iostream>
using namespace std;
int a[50000];
int main()
{
    int n = 0, k = 0;
    cin >> n >> k;
    for (int i = 0; i < n; i++)cin >> a[i];
    int res = 100000000;
    int ans1 = 0, ans2 = 0;
    for (int i = 0; i <= n - 2 * k; i++)
    {
        int tmp1 = 0,tmp2=0;
        for (int j = i; j < i + k; j++)
        {
            tmp1 += a[j];
        }
        int p = i + k;
        for (; p <= n-k; p++)
        {
            tmp2 = tmp1;
            for (int q = p; q < p + k; q++)
            {
                tmp2 += a[q];
            }
            if (tmp2 < res)
            {
                res = tmp2; ans1 = i+1; ans2 = p+1;
            }
        }
    }
    cout << ans1 << " " << ans2 << endl;
    return 0;
}

```

Answer 1

空间换时间的方法，用一个数组存放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;
}