Giải bài ntucoder LUTA - Luyện tập (OLPCĐ 2011)

Link bài:

Thuật toán:

• Để giải một bài có độ khó cao hơn trình độ hiện tại, ta cần hoàn thành các bài có độ khó trong tầm với để tích lũy kinh nghiệm. Con đường trên là duy nhất, điểm kinh nghiệm là vô nghĩa nếu độ khó của bài là quá cao.
  
• Bằng tư duy đó, ta sẽ sắp xếp các bài với độ khó tăng dần và giải theo thứ tự.

Code:

Mã:

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

pair <int, int> a[100007];
int n, c, ans, pos = 1;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("luta.inp", "r", stdin);
    //freopen("luta.out", "w", stdout);
    cin >> n >> c;
    for (int i = 1; i <= n; i++) cin >> a.fi >> a.se;
    sort(a+1, a+1+n);
    while (pos <= n){
        if (a[pos].fi > c) break;
        c += a[pos].se;
        ans++; pos++;
    }
    cout << ans;

    return 0;
}