[TIOJ 1884][IOI 2015] Boxes

原題連結
剛好最近作到一些類似的問題，所以這題的核心思想我是矇中的(?
先給出一個結論：
必定存在某一最優解，使得存在一交界點M，從0~M的隊伍皆是順時針走訪到，而從M+1~N的隊伍是逆時針走訪到。

這個思想跟這題很像，剛好就是前天做到的XDDD。

所以主算法過程就很清晰了，我們枚舉交界點M，在O(1)的時間內算出每次枚舉能得到的答案是多少，然後更新ans。

至於要怎麼O(1)算出答案呢？思想也跟上面提到的那題很像。預處理出順時針和逆時針到每一點的最短花費，枚舉M的時候直接兩個陣列做相加。
這可以直接greedy也可以用類似DP的方法下去做。

建議不要greedy...算某個點的回去時間很麻煩的orz

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL INF=(1LL<<60);
vector<LL> pos,pre,suf;
inline LL readLL()
{
    char c;
    LL ret=0;
    c=getchar();
    for(;c>'9' && c<'0';) c=getchar();
    for(;c<='9' && c>='0';) {ret=ret*10LL+c-'0';c=getchar();}
    return ret;
}
int main()
{
    LL T;
    T=readLL();
    while(T--)
    {
        LL N,K,L;
        N=readLL();K=readLL();L=readLL();
        pos.clear();pre.clear();suf.clear();
        pos.resize(N+2);pre.resize(N+2);suf.resize(N+2);
        
        for(LL i=1;i<=N;i++) pos[i]=readLL();

        pos[0]=0;pre[0]=0;
        for(LL i=1;i<=N;i++) pre[i]=(i-K>=0?pre[i-K]+pos[i]:pos[i])+min(pos[i],L-pos[i]);
        
        pos[N+1]=L;suf[N+1]=0;
        for(LL i=N;i>=1;i--) suf[i]=(i+K<=N+1?suf[i+K]+L-pos[i]:L-pos[i])+min(pos[i],L-pos[i]);
        
        LL ans=INF;
        for(LL i=0;i<=N;i++) ans=min(ans,pre[i]+suf[i+1]);
        printf("%lld\n",ans);
    }
}