题解：P5849 [IOI2015] boxes

· · 题解

这道题难点是想清楚最佳情况该怎么走。首先我们观察到要想走的越少，我们每次肯定会拿足物品，并且全部发放完才回来。这个很好理解，因为拿多一点物品并不会有什么代价，我们也不会还剩着东西就走回来，否则我们还得拿东西再走一趟这样得走更久。

第二是我们不会跳过人不给，因为跑到远处回来再补上跳过的人，和连续给完回来再跑到远处是一样的。以上总结一下就是每次我们会拿足 K 个纪念品并且分给连续的 K 个人，直到大家都有纪念品。

其次我们观察到大多数情况都是从哪出发，送完后从哪原路返回。而只有一种情况是会走一周回到原点，就是送完东西已经超过了中点了，这样原路返回就不如继续走完回来了。

走一周这个动作我们至多只会做一次。因为我们只会在送这 K 个纪念品时越过了中点，才会走一周。越过一次中点后中点两边的人都给了，所以就不可能再会过中点了。

假设我们会走一周。那么我们就枚举所有穿过中点的 K 个人。答案就是这 K 个人左右做送东西原路返回所需的时间，加上走一圈的时间。如图所示，假设红线为中点，底部为起点。我们枚举每个这样包含 K 个人的蓝色区间让他走一周即可。

假设我们不会走一周，那就更简单了，直接让中点左右都做送东西原路返回，答案是左右两边加起来。

实现的话可以使用动态规划。设 dp_i 为以第 i 个元素作为送东西原路返回的终点所需的时间。若 i 在左半部分的话转移方程是 dp_i=p_i+dp_{i-k}，在右边则是 dp_i=L-p_i+dp_{i+k}。注意我们并不关心每个区域有几个人，我们只关心人在哪个区域。

以下是代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,k,l;
int a[10000005];
int dp[10000005];
bool right(int i){
    return a[i]>=(l+1)/2;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k>>l;
    for (int i=1;i<=n;i++) cin>>a[i];
    int b;
    for (int i=1;;i++) {
        if (right(i)) {
            b=i;
            break;
        }
        dp[i]=a[i]+dp[max(0ll,i-k)];
    }
    for (int i=n;right(i);i--) dp[i]=l-a[i]+dp[min(n+1,i+k)];
    int ans=21000000000000000;
    for (int i=1;i<=n;i++){
        if (i+k-1<b) continue;
        if (i+k-1>n||i>=b) break;
        ans=min(ans,2*dp[i-1]+2*dp[i+k]+l);
    }
    cout<<min(ans,dp[b-1]*2+dp[b]*2);
    return 0;
}