ACコード
Submission #8499609 - AtCoder Beginner Contest 131
int main()
{
cout <<setprecision(10);
ll n; cin >> n;
vector<pair<int,int>> task(n);
rep(i,n) {
ll a,b;
cin >> a >> b;
task[i] = make_pair(b,a);//task 締め切り、かかる時間
}
SORT(task);
ll time = 0 ;
rep(i,n){
ll a,b ;
tie(b,a) = task[i];
time += a;
if(time > b){
cout <<"No"<<endl;
return 0 ;
}
}
cout <<"Yes" <<endl;
}解法
締め切りが近づいているものは早く終わらせよう
例えば、
タスク１締め切りが 5分、かかる時間が1分
たすく２締め切りが 5 分 かかる時間が2分
みたいなとき（たとえがおそらく適切でない）
タスク1、2の順でやっても、タスク2,1の順番でやっても、間に合うときは間に合うし、間に合わないときは間に合わないんですよね。
締め切りが5分のもののかかる時間の総計が結局のところ5分で終わらなきゃいけない。
みたいな感じ。
証明 ↓
Task 1 A1,B1,
Task 2 A2,B2
(B1 <= B2)
Bが小さい順にタスクをしたほうがいいことを示す
1 2 の順でやるときには
A1 <= B1 && A1+A2 <= B2を満たせればいい これを条件①
2 1の順でやるときは
A2 <= B2 && A2 + A1 <= B1 を満たせればいい これを条件②
締め切りが近い順にやればいいってことを示すには、
条件①のほうが緩いことが示せればいい
条件②を満たしていて条件①を満たせてないのがなければいい
条件①のA1 <= B1 を満たさないとき、
条件②の A2 + A1 <= B1 は当然満たせない
次
条件①の A1 + A2 <= B2が満たされていないとき
条件②の A2 + A1 <= B1 は、 B1がB2より小さいので当然満たされない
よって ①が無理なら②も満たしていない
これで証明終わり
らしい
