AOJ : 0231 - Dangerous Bridge (危ない橋)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0231&lang=jp
日本語の問題文なので説明省略です.

アルゴリズム

ある時間において, 体重の変動がいくらであるかを記憶するMapを作成しておきます(プログラム内のsc).
あとは, 時間の早い方から順番に, マップの変動の値を足していって, 途中で150を超えるならNGと表示します.

プログラム

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

typedef pair<int,int> P;

int n;
map<int,int> sc;

int main(void){
  while(cin>>n,n){
    sc.clear();

    for(int i=0;i<n;i++){
      int m,a,b;
      cin>>m>>a>>b;
      sc[a] += m;
      sc[b] -= m;
    }

    vector<P> v;
    for(map<int,int>::iterator iter=sc.begin();iter!=sc.end();iter++){
      v.push_back(P(iter->first,iter->second));
    }
    sort(v.begin(),v.end());

    int w = 0;
    int i;
    for(i=0;i<v.size();i++){
      w += v[i].second;
      if(w > 150){
        break;
      }
    }
    cout<<(i==v.size() ? "OK" : "NG")<<endl;
  }

  return 0;
}