1 条题解

  • 0
    @ 2023-8-31 16:51:22
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 1000000;
    int n, k;
    long long a[MAXN + 5], sum[MAXN + 5];
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n >> k;
        a[1] = 0;
        for (int i = 2; i <= n; i++)
            cin >> a[i];
        // 预处理 sum[]
        sum[1] = 0;
        for (int i = 2; i <= n; i++)
            sum[i] = sum[i - 1] + a[i];
        // 找到长度为 k 的子段中,子段和最大的一段的和
        int l = 1, r = 1 + k;
        long long maxSumK = sum[r] - sum[l];
        for (; r <= n; l++, r++)
            maxSumK = max(maxSumK, sum[r] - sum[l]);
        // 答案为 sum[n] - maxSumK
        cout << sum[n] - maxSumK << "\n";
        return 0;
    }
    
    • 1

    信息

    ID
    1327
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    6
    已通过
    5
    上传者