Yuki 198 キャンディー・ボックス2 ( Ternary Search )
No.198 キャンディー・ボックス2 - yukicoder
自分の普段の書き方がバグりまくって解説を見た。
mmxsrup.hatenablog.com
注意すべきことは自分の ok() の返す値は gol がある上限を超えると不可能として INF とする。それが関数の右部分を平らかにする、なので3分探査の際は <= で比較する。
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll ok( int b, const vector< int > &c, int gol ){ ll res = 0; ll x = b; for( int i = 0; i < c.size(); ++i ) if( c[ i ] > gol ) x += c[ i ] - gol, res += c[ i ] - gol; for( int i = 0; i < c.size(); ++i ) if( c[ i ] < gol ) x -= gol - c[ i ], res += gol - c[ i ]; if( x < 0 ) return 1LL << 62; return res; } signed main(){ int B; cin >> B; int N; cin >> N; vector< int > C( N ); for( int i = 0; i < N; ++i ) cin >> C[ i ]; if( N == 1 ) cout << 0 << endl, exit( 0 ); int lb = 0, rb = ( int ) 1e9; while( rb - lb > 3 ){ int x = ( 2LL * lb + rb ) / 3; int y = ( 2LL * rb + lb ) / 3; if( ok( B, C, x ) <= ok( B, C, y ) ) rb = y; else lb = x; } ll ans = 1LL << 62; for( int i = lb; i <= rb; ++i ) ans = min( ans, ok( B, C, i ) ); cout << ans << endl; return 0; }