[AtCoder] ABC 131 D – Megalomania
問題
方針
締め切り時刻である \( B \) の値が小さいものから仕事を終わらせていくシミュレーションを行います。ある仕事が終わった時の時刻を \( t \) とすると、次に取り掛かる仕事 \( i \) が、\( t + A_i \leq B_i \) を満たしていないと、不可能です。もし、可能ならば、時刻は \( t + A_i \) として、次の仕事をできるかどうかのチェックをします。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Data { ll A, B; Data(ll A, ll B) : A(A), B(B){} bool operator< (const Data& d) const { return B < d.B; } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; ll A[N], B[N]; for (int i = 0; i < N; i++) { cin >> A[i] >> B[i]; } vector<Data> v; for (int i = 0; i < N; i++) { v.push_back(Data(A[i], B[i])); } sort(v.begin(), v.end()); ll t = 0; for (int i = 0; i < N; i++) { if (t + v[i].A <= v[i].B) { t += v[i].A; } else { cout << "No\n"; return 0; } } cout << "Yes\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません