题解 P5638 【【CSGRound2】光骓者的荣耀】

Eason_AC · 2019-11-10 18:52:43 · 题解

感觉这次月赛的第二题比第一题还简单，但是第一题思路还是比较明晰的。

这里我们利用了前缀和的思想，我们可以在边输入的时候边处理前缀和。

那么这里前缀和有什么用呢？我们可以发现，这道题目本质就是让你找到长度为k的最大连续子段和。拿总长度减去这个最大连续子段和就是我们想要的答案啦！

代码实现的时候注意，Karry弄的非常良心的数据范围，不开long long见祖宗！

好了，所以这道题目就做完了，下面奉上AC代码，不懂的可以参考一下：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
#define ll long long

ll n, k, a[1000007], s[1000007], tmp;

int main() {
    scanf("%lld%lld", &n, &k);
    for(ll i = 1; i < n; ++i) {
        scanf("%lld", &a[i]);
        s[i] = s[i - 1] + a[i];
//      printf("%lld:%lld\n", i, s[i]);
    } 
//  if(!k) {
//      printf("%lld", s[n - 1]);
//      return 0;
//  }
    ll maxi = s[k];
//  printf("First it was: %lld\n", maxi);
    for(ll i = k + 2; i < n; ++i) {
//      printf("%lld %lld %lld %lld\n", i, k, s[i], s[i - k]);
        maxi = max(maxi, s[i] - s[i - k]);
//      printf("Max changed to %lld\n", maxi);
    }
    printf("%lld", s[n - 1] - maxi);
    return 0;
}