洛谷P5638《光骓者的荣耀》解题报告

男娘i 2023-07-08 15:29 8阅读 0赞

# 一、题目 #

https://www.luogu.com.cn/problem/P5638

# 二、分析 #

![在这里插入图片描述][20200226225234398.png]  
上图是一个n = 6的样例。从城市1到城市6，需要3+2+4+5+4=18天。

假如传送器的半径为2。可以逐个枚举。

如果在城市1使用传送器，则一下子可到达城市3，然后城市3到城市6，需要13天。这种情况下从城市1到城市6，需要13天。

如果在城市2使用传送器，则从城市1先用3天的时间到达城市2，再用传送器到达城市4，从城市4到城市6需要9天。这种情况下从城市1到城市6，共需要3 + 9 = 12天。

如果在城市3使用传送器，则从城市1到城市3需要5天，从城市3使用传送器一下子到达城市5，从城市5到城市6需要4天。这种情况下从城市1到城市6，共需要5+4=9天。

如果在城市4使用传送器，则从城市1到城市4需要9天，从城市4使用传送器一下子到达城市6。这种情况下从城市1到城市6，共需要9天。

如果在城市5使用传送器，则从城市1到城市5需要14天，从城市5使用传送器一下子到达城市6。这种情况下从城市1到城市6，共需要14天。

所以在城市3或城市4使用传送器，可以使得总共花费的时间最少。

# 三、AC代码 #

#include <iostream>
    #include <climits>
    using namespace std;
    
    const int maxN = 1000000 + 5;
    long long n, k;
    long long a[maxN];
    long long sum[maxN];
    long long ans = LLONG_MAX;//9223372036854775807
    
    int main()
    {
        cin >> n >> k;
        for(int i = 2; i <= n; i++)//i代表第i个城市
        {
            cin >> a[i];//a[i]代表第i-1个城市到第i个城市需要的时间
            //利用前缀存储从第1个城市到第i+1个城市的累积时间
            sum[i] = sum[i - 1] + a[i];
        }
    
        for(int i=1; i<=n; i++) //i代表第i个城市
        {
            int far = i + k; //传送到最远的点
            if(far >= n)
            {
                far = n;    //最远不能超过n点
            }
            long long time = sum[i] + sum[n] - sum[far];
            ans = min(ans, time);   //取最小值
        }
    
        cout << ans << endl;//输出
        return 0;
    }

代码分析：

以上图中的数据为例。

sum\[\]数组是前缀和。sum\[1\] = 0表示从第一个城市到第一个城市用的累加时间是0天。

第一个for里：

i = 2时，输入a\[2\]=3表示从第一个城市到第二个城市需要3天。sum\[2\]=sum\[1\]+a\[2\]=0+3=3，表示从第一个城市到第二个城市需要3天。

i = 3时，输入a\[3\]=2表示从第二个城市到第三个城市需要2天。sum\[3\]=sum\[2\]+a\[3\]=3+2=5天。表示从第一个城市到第三个城市需要5天。

i = 4时，输入a\[4\]=4表示从第三个城市到第四个城市需要4天。sum\[4\]=sum\[3\]+a\[4\]=5+4=9天。表示从第一个城市到第四个城市需要9天。

i = 5时，输入a\[5\]=5表示从第四个城市到第五个城市需要5天。sum\[5\]=sum\[4\]+a\[5\]=9+5=14天。表示从第一个城市到第五个城市需要14天。

i = 6时，输入a\[6\]=4表示从第五个城市到第六个城市需要4天。sum\[6\]=sum\[5\]+a\[6\]=14+4=18天。表示从第一个城市到第六个城市需要18天。

第二个for中，

i = 1时，far = 3，表示从第一个城市用传送器一下子传到第三个城市，time=sum\[1\] + sum\[6\] - sum\[3\] = 0 + 18 - 5 = 13天。sum\[6\]-sum\[3\]表示从第三个城市到第六个城市所需的时间。

i = 2时，far = 4，表示从第二个城市用传送器一下子传到第四个城市，所用的时间time = sum\[2\] + sum\[6\] - sum\[4\] = 3 + 18 - 9 = 12天。这里sum\[2\]表示从第一个城市到第二个城市所需的时间。sum\[6\]-sum\[4\]表示从第四个城市到第六个城市所需的时间。

i = 3时，……

> =======================================  
> 了解信息学奥赛请加微信307591841或QQ群581357582

[20200226225234398.png]: https://img-blog.csdnimg.cn/20200226225234398.png