2705 Overflowing Bookshelf

問題概要

幅sの本棚に本を出し入れする。
本を入れるときは、本の幅wおよびidが与えられ、
本を棚の左端に挿入する。その際にもとあった本は右に動き、本棚の右端を超えた本は落下する。


操作終了後に棚に残っている本のidを、左から順に出力せよ。

解法

本棚から取り出した本の部分には穴があく、とあるが、結果には全く影響しない。
したがって、それを無視してシミュレートできる。


今入れている本の総量が本棚の幅を超えたら右端から本を取り除いていく。

ソースコード

struct B{
	int id,w;
	B(int id,int w):id(id),w(w){}
};
int s; vector<B> b;

int main(){
	int cs=1;
	while(scanf("%d",&s),s>=0){
		b.clear();
		char c; int w,id;
		while(scanf(" %c",&c),c!='E')
		{
			scanf("%d",&id);
			if(c=='R')
			{
				rep(i,b.size())if(b[i].id==id)
				{
					b.erase(b.begin()+i); break;
				}
				continue;
			}
			scanf("%d",&w);
			int sum=0;
			rep(i,b.size())
			{
				sum+=b[i].w;
				if(sum+w>s)
				{
					b.erase(b.begin()+i,b.end());
					break;
				}
			}
			b.insert(b.begin(),B(id,w));
		}
		printf("PROBLEM %d:",cs++);
		rep(i,b.size())printf(" %d",b[i].id);
		puts("");
	}
	return 0;
}