「AOJ231～240」の編集履歴（バックアップ）一覧に戻る

---

「AOJ231～240」を以下のとおり復元します。

---

*0231　Dangerous Bridge
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0231
橋の通行記録から橋が壊れるほどの重量がかかってないかを調べる問題。

解法
わたる順番と橋を渡り終える順番に並べて一からシミュレートするだけです。

 #include<stdio.h>
 #include<queue>
 struct move{
	int w,type,time;//wは重さ、0がわたり終わり1がわたり始め
	bool operator<(const move m)const{
		if(time!=m.time) return time>m.time;
		return type>m.type;
	}
 };
 void setData(int n){
	std::priority_queue<move> qu;
	move m;
	int last;
	for(int i=0;i<n;i++){
		scanf("%d %d %d",&m.w,&m.time,&last);
		m.type=1;
		qu.push(m);
		m.type=0;
		m.time=last;
		qu.push(m);
	}
	int allW=0;
	bool allOK=true;
	while(!qu.empty()){
		m=qu.top();
		qu.pop();
		if(m.type==0){
			allW-=m.w;
		}else{
			allW+=m.w;
		}
		if(allW>150){
			allOK=false;
			break;
		}
	}
	printf("%s\n",allOK?"OK":"NG");
 }
 int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		setData(n);
	}
 }

---

復元してよろしいですか？