けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 131 D - Megalomania (400 点)

いわゆる、「必要条件を列挙したら十分条件になっている」というタイプの教育的な Greedy 問題!!!

問題へのリンク

問題概要

 N 個の仕事があって、仕事  i は、 A_i の時間を要し、時刻  B_i までに終わらなければならない。

時刻 0 に仕事を開始する。 N 個の仕事をすべて完遂することが可能かどうかを判定せよ。

制約

  •  1 \le N \le 2 \times 10^{5}

考えたこと

一見手がつかない雰囲気がして怖い問題という印象がある。直感的には、締め切りが早いものから順にやっていくべきなように思える。ちゃんと順を追って考えてみよう。

必要条件を列挙

当然満たすべきこととして、

時刻  t が締め切りの仕事があったとして、時刻  t 以前に締め切りのある仕事は、時刻  t までに終わらなければならない

ということが言える。そして、実はこの条件は十分条件でもある。つまり、この条件さえ満たしていれば、仕事を完遂することができるのだ!!!!!!

その証明は、まさに下の「解法」に示すアルゴリズムによって、実際に完遂できることを示せることから言える。

解法

最終的な解法はとてもシンプルに、

  • 締め切りの時刻が早い順に仕事をソートして
  • その順序で仕事を順にやっていき
    • 終了時刻が締め切り後になる箇所が発生したらダメ
    • 発生しなければ実際にすべての仕事を完遂できている

ということになる!!!

もし上の必要条件を満たしていなかったら途中でダメになるし、必要条件を満たしていたらこのアルゴリズムを完走できて、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;
}