0w1

IOI 15 Boxes with Souvenirs ( Greedy )

PEG Judge - IOI '15 - Boxes with Souvenirs
実はそんなに難しくない Greedy。まず、どういう操作があるか考えてみよう。
1、時計回りに動いて逆時計回りに戻る
2、1の真逆
3、一周する
1をする場合は半周を過ぎないのは簡単に見える(そうする必要があったら、2をした方が絶対いい)。
1と2はO( n )で
cw[ i ] : 時計回りして逆時計回りで戻る、だけをして i人に渡した時の最小distanceみたいなものを計算する。
すると3を無視したら、答えは min{ cw[ i ] + cw[ n - i ] } だと分かる。
でも3は一体なんだろう、ちょっと想像してみると、円を横から半分に切って、左下と右下の人に同時にあげたい時だけ発生する。しかしもし左半か右半のどちらかが k人以上いれば、やはり1と2を別々にした方がよさそう。
もう少し考える。じゃあその時はその時で先にk - 1人以下になるよう1と2だけで省略してみよう。すると直感的にわかる。3は最大1回しか発生しない。3の本質はつまり真ん中から Lのコストで k人取ってくれる。
なので3のある場合の min{ cwdis[ i ] + L + ccwdis[ n - k - i ] } も全部一通り試してみる。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e7 + 7;
const int MAXK = MAXN;
const int MAXL = 1e9 + 9;
#define int long long

int n, k, l;
int pep[ MAXN ];

int cwdis[ MAXN ]; // minimum distance only going clockwise giving i pep
int ccwdis[ MAXN ];
void solve(){
    for(int i = 0; i < n; ++i){
        int lstdis;
        if( i + 1 > k ) lstdis = cwdis[ i + 1 - k ];
        else lstdis = 0;
        cwdis[ i + 1 ] = lstdis + pep[ i ] * 2;
        // cout << " cwdis[ " << i + 1 << " ] : " << cwdis[ i + 1 ] << endl;
        // if( ( i + 1 ) % k == 0 ) lstdis = cwdis[ i + 1 ];
    }
    for(int i = n - 1; i >= 0; --i){
        int lstdis;
        if( n - i > k ) lstdis = ccwdis[ n - i - k ];
        else lstdis = 0;
        ccwdis[ n - i ] = lstdis + ( l - pep[ i ] ) * 2;
        // cout << " ccwdis[ " << n - i << " ] : " << ccwdis[ n - i ] << endl;
        // if( ( n - i ) % k == 0 ) lstdis = ccwdis[ n - i ];
    }
    int ans = 1e17;
    for(int i = 0; i <= n; ++i)
        ans = min( ans, cwdis[ i ] + ccwdis[ n - i ] );
    for(int i = 1; i + k - 1 <= n; ++i) // one circle for [ i, i + k - 1 ] cw
        ans = min( ans, cwdis[ i - 1 ] + l + ccwdis[ n - ( i + k - 1 ) ] );
    cout << ans << endl;
}

signed main(){
    ios::sync_with_stdio( false );
    cin >> n >> k >> l;
    for(int i = 0; i < n; ++i)
        cin >> pep[ i ];
    solve();
    return 0;
}