本番こっちの方が楽に通せた。
https://codejam.withgoogle.com/2018/challenges/0000000000007883/dashboard/000000000002fff6
問題
C個のレジのうち最大R個を使って計B個の商品を買う。
各レジiは3つのパラメータM[i],P[i],S[i]で定められる。
M[i]はそのレジで買える最大商品数、P[i]は購入手続きの時間、S[i]は商品1個あたりのスキャンにかかる時間である。
最適なレジの選択をしたとき、B個の商品を買う最短時間を求めよ。
解法
時間で二分探索すればよい。
時間を決めれば各レジで返る商品数が決まるので、上位R個を利用する。
int T,testcase; int R,C; ll B; ll M[1010],S[1010],P[1010]; ll ok(ll v) { int i; vector<ll> c; FOR(i,C) { if(v<P[i]) continue; c.push_back(min(M[i],(v-P[i])/S[i])); } sort(ALL(c)); reverse(ALL(c)); ll tot=0; FOR(i,min((int)c.size(),R)) tot+=c[i]; return tot>=B; } void solve(int TC) { int i,j,k,l,r,x,y; string s; cin>>R>>B>>C; FOR(i,C) { cin>>M[i]>>S[i]>>P[i]; } ll ret=(1LL<<60)-1; for(i=59;i>=0;i--){ if(ok(ret-(1LL<<i))) ret-=1LL<<i; } _P("Case #%d: %lld\n",TC,ret); }
まとめ
これは定番テクだね。