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

· · 题解

题解原因

这篇题解旨在帮助理解，dalao请忽视。

因为这是一道\color{red}\text{红题}，所以我在这里讲述的详细一点。

题目简介

有 n 个城市，每两个城市之间有双向通路，耗费时间 a_{i} (其实可以理解为长度为 a_{i} ) ，小K从 {1-n} 走访 (可以理解为从1走到 n )。

但是小K可以从第 i 个城市直接跳转到第 i-k 或 i+k 。(只可使用一次)

注意：他可以不访问所有的城市，使用传送器不耗费时间 (这句话意味着上面的跳转方案的思路是正确的，比如我完全可以从城市 1 跳到城市 4 ，只要使小K走过的总长度最短就可以)

求最快的用时 (即求最短的走路长度)。

思路分析

结合样例，我们可以发现，我们最终走过的长度就是\color{red}\text{总长度-跳转的长度}，输入的 k 即为我们跳转的范围。

总长度使一个固定值，即所有路径的长度和。

那么要使得最终走过的长度最短，只需使跳转的长度最大。

我们只需要在所给的 a_{i} 中选取 k 个数，使得 \sum\limits_{i=x}^{x+k}a_i 的值最大即可。

我们可以枚举每一个 k 的范围，求 ∑ ，在这里放一份实现代码：

for (int i = 1; i <= n; i++) {
    long long ans2 = 0;
    for (int j = 0; j < k; j++) {
        ans2 += cxk[i + j];
    }
    maxx = max(maxx, ans2);
}

但是我们会发现这个毒瘤数据范围（注意看21~25）

显然这样循环会重复计算中间的一些值，21~25都会超时。

那么我们怎么优化呢？

优化

我们可以在循环的基础上，去掉重复计算的值。

在从 a_{1} 到 a_{k} 求和的基础上，加上第 a_{k+1} 个数，减去 a_{1} ，是不是就可以去掉重复计算的值了？ 依然取其最大，我们可以这样写：

a = 0, b = a + k;
for (int i = a; i < b; i++)
    ans2 += cxk[i];
for (int i = 1; i <= n - k; i++) {
    ans2 = ans2 + cxk[b] - cxk[a];
    maxx = max(maxx, ans2);
    a++, b++;
}

当然输出时应该输出总长度-跳转的长度，

cout << ans - maxx;

这就是核心代码了，最后把 头文件及初始化一写：

#include <bits/stdc++.h>
using namespace std;
int n, k, a, b;
long long cxk[1000010], ans, maxx, ans2;

数据读入：

ios::sync_with_stdio(false);
cin >> n >> k;
for (int i = 1; i <= n - 1; i++)
   cin >> cxk[i], ans += cxk[i];

最后

return 0;