AOJ_0231 Dangerous Bridge
問題
解法
優先順位付きキューを使って橋にかかる重さの変化を管理するとやりやすい。
体重Mの人が時刻Aに橋を渡り始めた---> (A, M)をプッシュ
体重Mの人が時刻Bに橋を渡り終えた---> (B, -M)をプッシュ
すべてキューにつっこんだあと、時刻の小さいほうから取り出していき
取り出した重さを変数に足していく。
重さの和が150を越えることがなかったらセーフ。
#include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; typedef pair<int, int> P; int main(){ int n; while(scanf("%d", &n) && n){ priority_queue<P, vector<P>, greater<P> > que; for(int i = 0; i < n; i++){ int m, a, b; scanf("%d %d %d", &m, &a, &b); que.push(P(a,m)); que.push(P(b,-m)); } int s = 0; bool f = true; while(!que.empty()){ s += que.top().second; que.pop(); if(150 < s){ f = false; break; } } printf("%s\n", f?"OK":"NG"); } return 0; }