题解 P5849 【[IOI2015]boxes 纪念品盒】

2020-01-08 18:47:09


广告


好久以前做的题了,看到没人写题解就来补一下。

想一想发现只有以下三种路线:

  • 顺时针去,逆时针回;
  • 顺时针去,顺时针回;
  • 逆时针去,顺时针回。

再进一步可以发现,第二种路线只会走至多一次,因为多走可以用一或三替换,答案不会变差。

于是枚举左半边有多少个点通过第一种路线送到,然后剩下的点和右半边最左边的一些点组成第二条路线送到的点。

那么此时的时间就是第一条路线的时间加第三条路线的时间加 $L$ 。预处理出第一条路线和第三条路线的时间即可 $O(1)$ 计算。

具体实现及细节见代码。

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000000+10;

int n,k,l;
int sta1[N],top1=0; ll sum1[N];
int sta2[N],top2=0; ll sum2[N];

int main() {
    n=read(),k=read(),l=read();
    for (re int i=1;i<=n;++i) {
        int p=read();
        if (p<=l/2) sta1[++top1]=p;
        else sta2[++top2]=l-p;
    }
    reverse(sta2+1,sta2+top2+1);
    for (re int i=1;i<=top1;++i) {
        if (i<=k) sum1[i]=sta1[i];
        else sum1[i]=sum1[i-k]+sta1[i];
    }
    for (re int i=1;i<=top2;++i) {
        if (i<=k) sum2[i]=sta2[i];
        else sum2[i]=sum2[i-k]+sta2[i];
    }
    ll ans=2*(sum1[top1]+sum2[top2]);
    for (re int i=top1-k;i<=top1;++i)
        ans=min(ans,2*(sum1[i]+sum2[max(0,top2-k+top1-i)])+l);
    printf("%lld\n",ans);
    return 0;
}