Algoogle

Algorithm for Programming Contest

AOJ 1052 Old Bridges

Category: AOJ Tag: greedy

Old Bridges

問題概要


解法


橋の許容量が小さいところから渡っていけばいい

コード


(1052.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
#define rep(i, b) for(int i = 0; i < b; i++)
#define pb push_back
using namespace std;
typedef pair<int,int> P;

int main(){
    int n;
    while(cin >> n, n){
        vector<P> br;
        rep(i,n){
            int a, b;
            cin >> a >> b;
            br.pb(P(b,a));
        }
        sort(br.begin(),br.end());
        int w = 0;
        rep(i,n){
            if(w + br[i].second <= br[i].first) w += br[i].second;
            else {
                w = -1;
                break;
            }
        }
        if(w==-1) cout << "No\n";
        else cout << "Yes\n";
    }
}

Comments