AtCoder ABC 131 D - Megalomania (茶色, 400 点)

いわゆる、「必要条件を列挙したら十分条件になっている」というタイプの教育的な 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;
}