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; }