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

vеctorwyx · 2019-11-10 14:32:02 · 题解

一道简单的贪心

枚举每一种传送方式

直接上代码

#include<iostream>
using namespace std;
long long n,k,a[1000010],dp[1000010],minx,ji,shi;
int main()
{
    cin>>n>>k;
    for(int i=1;i<n;i++)
    {
        cin>>a[i];
        shi+=a[i];//总时间（不传送）
    }
    if(k>0)
    for(int i=1;i<=n-k;i++)//枚举每一种传送方式
    {
        if(i==1)
        for(int j=i;j<i+k;j++)
        {
            ji+=a[j];//一开始就传送
        }
        else
        {
            ji-=a[i-1];//去掉前一个时间
            ji+=a[i+k-1];//加上后一个时间
        }
        if(ji>minx)
        minx=ji;//寻找最大用时进行传送
    }
    cout<<shi-minx;//减去传送节约的时间
} 

求管理员给通过