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

Anye
Anye
发布于 2019-11-10 / 4 阅读
0
0

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

题解原因

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

因为这是一道红题红题所以我在这里讲述的详细一点。

题目简介

𝑛n 个城市,每两个城市之间有双向通路,耗费时间 𝑎𝑖ai (其实可以理解为长度为 𝑎𝑖ai ) ,小K从 1−𝑛1−n 走访 (可以理解为从1走到 n )

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

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

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

思路分析

结合样例,我们可以发现,我们最终走过的长度就是总长度-跳转的长度总长度-跳转的长度,输入的 𝑘k 即为我们跳转的范围。

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

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

我们只需要在所给的 𝑎𝑖ai 中选取 𝑘k 个数,使得 ∑𝑖=𝑥𝑥+𝑘𝑎𝑖i=xx+kai 的值最大即可。

我们可以枚举每一个 𝑘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都会超时。

那么我们怎么优化呢?

优化

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

在从 𝑎1a1𝑎𝑘ak 求和的基础上,加上第 𝑎𝑘+1ak+1 个数,减去 𝑎1a1 ,是不是就可以去掉重复计算的值了? 依然取其最大,我们可以这样写:

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;


评论