Old Bridges｜AOJ

Old Bridges | Aizu Online Judgeを解きました。

#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
using namespace std;
int main (){
      
    cin.tie(0);
    ios::sync_with_stdio(false);
      
    while( true ){
        int N;
        cin >> N;
        if( N == 0 ){ break; }
        multimap<int, int> mp;
        REP( i, N )
        {
            int a, b;
            cin >> a >> b;
            mp.insert( make_pair( b, a ) );
        }
        int total{};
        bool flag = true;
        for( const auto& x : mp )
        {
            total += x.second;
            if( total > x.first )
            {
                flag = false;
            }
        }
        cout << ( flag ? "Yes" : "No" ) << endl;
    }
    return 0;
}

某氏から貪欲法を使う簡単な問題という事でサジェストされて解きました。
最初std::mapで解いていたのですがWAしてしまい...
なんか要素数足りない！出力値がおかしい！ってなったのですけど、
std::mapって重複を許可されないんですね...。
無限に出力値が足りない訳です...。
調べるとstd::multimapという多重連想配列クラスがあったのでそちらに変更。
各キーに対する値を複数持つことができるので重複可です。
std::multimapに変えたらAC出来ました！

#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
using namespace std;
int main (){
       
    cin.tie(0);
    ios::sync_with_stdio(false);
       
    while( true ){
        int N;
        cin >> N;
        if( N == 0 ){ break; }
        vector<pair<int,int> > vc(N);
        for( auto& x : vc )
        {
            cin >> x.second >> x.first;
        }
        sort( vc.begin(), vc.end() );
        int count{};
        bool flag = true;
        for( auto& x : vc )
        {
            count += x.second;
            if( count > x.first )
            {
                flag = false;
            }
        }
        cout << ( flag ? "Yes" : "No" ) << endl;
    }
    return 0;
}

???「次はvectorで書き直してみよう」
書き直しました。
multimapで実装するより全然楽に実装できましたね...。
firstの値でsort出来るのは学びでした。

mapは楽しいけれどまだまだ不自由だ...。