前缀和【P5638 【CSGRound2】光骓者的荣耀】

题目大意

鉴于篇幅原因，就不展示原始题目了，需要的可去

P5638 【CSGRound2】光骓者的荣耀 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目大致意思为需要找到最短的那个点前往目标城市，中途可使用一次传送门（对i-k和i+k都可满足）

AC代码

#include 
#include
#include

using namespace std;

long long temp_ans[1000008];

int main()
{
    int n , k ;

    ios::sync_with_stdio(0);
    cin >> n >> k;

    temp_ans[0] = 0;
    for(int i = 1 ; i <= n - 1 ;i ++){
        cin >> temp_ans[i];
        temp_ans[i] += temp_ans[i - 1];
    }

    long long max_ans = 0;
    for(int i = 1 ; i <= n - k ; i ++){
        // 寻找最大的值（每一位都有前面所有的和）
        max_ans = max(max_ans , temp_ans[i + k - 1] - temp_ans[ i - 1]);
    }
    cout << temp_ans[n - 1 ] - max_ans;

    return 0;
}

代码解释

题目最根本的目的就是求出最短的路程，而路程又和前面的路程有关。

前缀和

因此想到使用前缀和去保存每一次跳转的路程

即对于每个存放输入值都不是原始值，全部都为前面所有路径之和

for(int i = 1 ; i <= n - 1 ;i ++){
        cin >> temp_ans[i];
        temp_ans[i] += temp_ans[i - 1];
    }

找出最大的

因为传送器只能使用一次，因此我们需要将结果最优化，找出最大的值进行跳转

这里注意要用long long，因为对于测试用例来说ai>1e12

根据题意，我们知道传送门可直接跳转至当前下标+k或-k，因此我们只需要比较当前最大值和（当前下标+k-1）

为什么需要-1？

因为n个城市，只有n-1个距离。

因此对应数组的下标就需要-1，即当i = n- k时，比较的是当前最大值和temp_ans[n - 1]（数组最后一位）

long long max_ans = 0;
    for(int i = 1 ; i <= n - k ; i ++){
        max_ans = max(max_ans , temp_ans[i + k - 1] - temp_ans[ i - 1]);
    }

输出答案

因为最后一位保存的一定是当前全部路程之和，也就是说我们只需要将最后一位减去刚才通过循环得到的最大路程即可完成。

cout << temp_ans[n - 1 ] - max_ans;

---

总结与分析

其实我感觉这个题，如果知道前缀和这个概念将会十分的简单。

因为前缀和将会大大降低求和的时间，使得时间复杂度最小（因为在输入的时候，就执行相加的过程，几乎对时间复杂度不造成影响）

前缀和使用场景应当是 需要求全局和的情况，全局的和和每一个节点都有关，而且要根据不同的情况对路程进行修改

而且，若进行的 *** 作为跳跃时，可找出最大值，将当前局部和与当前最大值进行比较。

因为本题仅能跳跃一次，若需要满足跳跃多次，大致思路应该一致

• 依然需要执行前缀和 *** 作，因为所求结果不变（全局路程）

• 仅需要改变获取最大值的逻辑

  因为当前需要进行的多次获取最大值