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; }