DDPC16 B DDPC特別ビュッフェⅡ
http://discovery2016-final.contest.atcoder.jp/tasks/discovery_2016_final_b
二分探索+ちょっと気を使ったGreedy。
料理がN種類あって、回収される時間と美味しさがそれぞれ決まっています。また、一秒に一品しか料理をとれません。このとき取った料理の美味しさがxを超えるような最小の時間を求めろ、という問題。
最大値を与えるhogeの最小化というとやはり二分探索かなというのが第一感。なので、ある時間tに対し、t秒で美味しさxぶんの料理を取れるか判定できれば解けます。それをどうするかというと、結局貪欲法で十分なのですが、priority_queueやvectorから回収時間hoge秒のを取り除きます、というふうにすると実装が面倒です。なので時間を逆から辿って、回収時間hoge秒のをpriority_queueに追加、というふうにするとやりやすいです。まあなんだかんだ問題文を誤読しないのが一番のコツかなあという気もしますが。あとはオーバーフローに注意ですね。
const int MAX_N = 100100; int n, x; int t[MAX_N], a[MAX_N]; vector<int> dis[MAX_N]; ll check(int mt){ priority_queue<int> que; ll res = 0; for(int i = MAX_N; i > mt; --i) for(int a : dis[i]) que.push(a); for(int i = mt; i >= 1; --i){ for(int a : dis[i]) que.push(a); if(!que.empty()){ res += (ll)que.top(); que.pop(); } } return res; } int main(){ scanf("%d%d", &n, &x); rep(i, n) scanf("%d", t + i); rep(i, n) { scanf("%d", a + i); dis[t[i]].push_back(a[i]); } int lb = 0, ub = MAX_N; while(lb < ub){ int mid = (lb + ub) / 2; if(check(mid) >= (ll)x){ ub = mid; }else{ lb = mid + 1; } } if(lb > 100000) puts("-1"); else printf("%d\n", lb); return 0; }
こういう何でもない問題をサラっと解けるようになるといいのですが、いつもつまづいてしまいます。