2248.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2248 on 2006-05-23 at 11:53:44 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int CN = 1024;

class List {
	class Node {
	public:
		int o, pos, w;
		Node *nxt, *prev;
		Node(int co, int p, int cw) : o(co), pos(p), w(cw), nxt(NULL), prev(NULL) {}
	};
	Node* erase(const Node*);
	Node* push_front(int, int);
	Node *head, *tail, *it[CN];
public:
	int tw;
	List(int);
	~List();
	Node* begin() const { return head->nxt; }
	Node* end() const { return tail; }
	void insert(int, int);
	void remove(int o) { erase(it[o]); }
	void show() const;
};
List::List(int w) : tw(w) {
	head = new Node(-1, 0, 0); tail = new Node(-1, tw, 0);
	head->nxt = tail; tail->prev = head;
	int i;
	for(i = 0; i < CN; i++) it[i] = NULL;
}
List::~List() {
	int i;
	for(i = 0; i < CN; i++) 
		if(it[i] != NULL) delete it[i];
}
List::Node* List::erase(const Node* p) {
	p->prev->nxt = p->nxt;
	p->nxt->prev = p->prev;
	Node* r = p->prev; it[p->o] = NULL;
	delete p; return r;
}
List::Node* List::push_front(int o, int w) {
	Node *p = new Node(o, 0, w);
	head->nxt->prev = p; p->nxt = head->nxt;
	head->nxt = p; p->prev = head;
	return p;
}
void List::insert(int o, int w) {
	Node *p = it[o] = push_front(o, w);
	int pr = 0;
	for(; p != end(); p = p->nxt) {
		if(pr > p->pos) p->pos = pr;
		int cr = p->pos+p->w;
		if(cr > tw) p = erase(p);
		pr = cr;
	}
}
void List::show() const {
	Node *p;
	int r = 0;
	for(p = begin(); p != NULL; p = p->nxt) {
		if(r != p->pos) printf("blank %d\n", p->pos-r);
		if(p->o != -1) printf("%d %d\n", p->o, p->w);
		r = p->pos+p->w;
	}
}

int main()
{
	int w, t;
	char intro[16];
	
	for(t = 1; scanf("%d", &w) != EOF; t++) {
		if(t != 1) putchar('\n');
		List shelf(w);
		while(true) {
			int a, b; scanf("%s", intro);
			if(intro[0] == 'A') { scanf("%d %d", &a, &b); shelf.insert(a, b); }
			else if(intro[0] == 'R') { scanf("%d", &a); shelf.remove(a); }
			else break;
		}
		printf("Case %d:\n", t);
		shelf.show();
	}
	
	return 0;
}