いわゆる、「必要条件を列挙したら十分条件になっている」というタイプの教育的な Greedy 問題!!!
問題概要
個の仕事があって、仕事
は、
の時間を要し、時刻
までに終わらなければならない。
時刻 0 に仕事を開始する。 個の仕事をすべて完遂することが可能かどうかを判定せよ。
制約
考えたこと
一見手がつかない雰囲気がして怖い問題という印象がある。直感的には、締め切りが早いものから順にやっていくべきなように思える。ちゃんと順を追って考えてみよう。
必要条件を列挙
当然満たすべきこととして、
時刻 が締め切りの仕事があったとして、時刻
以前に締め切りのある仕事は、時刻
までに終わらなければならない
ということが言える。そして、実はこの条件は十分条件でもある。つまり、この条件さえ満たしていれば、仕事を完遂することができるのだ!!!!!!
その証明は、まさに下の「解法」に示すアルゴリズムによって、実際に完遂できることを示せることから言える。
解法
最終的な解法はとてもシンプルに、
- 締め切りの時刻が早い順に仕事をソートして
- その順序で仕事を順にやっていき
- 終了時刻が締め切り後になる箇所が発生したらダメ
- 発生しなければ実際にすべての仕事を完遂できている
ということになる!!!
もし上の必要条件を満たしていなかったら途中でダメになるし、必要条件を満たしていたらこのアルゴリズムを完走できて、Yes であることが確定するのだ。
#include <iostream> #include <vector> #include <algorithm> using namespace std; using pll = pair<long long, long long>; bool cmp(pll a, pll b) { return a.second < b.second; } int N; vector<pll> v; int main() { cin >> N; v.resize(N); for (int i = 0; i < N; ++i) cin >> v[i].first >> v[i].second; sort(v.begin(), v.end(), cmp); bool ok = true; long long sum = 0; for (int i = 0; i < N; ++i) { sum += v[i].first; if (sum > v[i].second) ok = false; } if (ok) cout << "Yes" << endl; else cout << "No" << endl; }