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

Leaved_ · 2019-11-10 18:08:44 · 题解

月赛红题

因为只能传送一次而且地图是线型的，所以传送到 i+k 一定比传送到 i-k 接近最优解

所以，利用 ma 数组存从 1 -> i 的距离，用 dis 存 “从 i 传送到 n 所花费用”

Code：

#include <bits/stdc++.h>

using namespace std;

long long n,k;
long long ma[1000010];
long long ans=LLONG_MAX;//9223372036854775807

long long dis[1000010];

int main() {
    cin>>n>>k;
    for(int i=2;i<=n;i++) {
        cin>>ma[i];
        ma[i]+=ma[i-1];
        //利用前缀和存储 1 -> i 的距离 
    }
    for(int i=1;i<=n;i++) {
        dis[i]=ma[i]+ma[n]-ma[i+k];//因为 往前传送 i+k 个点 一定比 往前传送 i+m （m < k）个点更接近最优解，所以直接加 
    }
    for(int i=1;i<=n;i++) {
        ans=min(ans,dis[i]);//取最小值 
    }
    cout<<ans<<endl;//输出 
}