2080.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2080 on 2005-11-12 at 12:15:56 */ 
#include <cstdio>
#include <cstring>

const int MAX = 10240;
const int INFINITE = 10000000;

class Queue {
	int top;
	int bottom;
	int queue[MAX];
	int oqueue[MAX];
public:
	void init();
	void push(int, int);
	bool isEmpty();
	int first();
	int pop();
};
void Queue::init() {
	top = bottom = 0;
}
void Queue::push(int e, int ord) {
	oqueue[bottom] = ord;
	queue[bottom++] = e;
}
bool Queue::isEmpty() {
	if(top != bottom) {
		return false;
	} else {
		return true;
	}
}
int Queue::first() {
	if(isEmpty()) {
		return INFINITE;
	} else {
		return queue[top];
	}
}
int Queue::pop() {
	int m = oqueue[top++];
	return m;
}

class Ship {
public:
	int loaded[MAX];
	int n;
	int limit;
	int time;
	int cross;
	Queue *now, *op;
	void init(Queue*, Queue*);
	void load();
	void change();
};
void Ship::init(Queue *n, Queue *o) {
	now = n;
	op = o;
	time = 0;
}
void Ship::load() {
	n = 0;
	while(!now->isEmpty() && now->first() <= time && n < limit) {
		loaded[n++] = now->pop();
	}
	if(n == 0) {
		if(now->first() < op->first()) {
			time += now->first() - time;
		} else {
			if(op->first() > time) {
				time += op->first() - time;
			}
			change();
		}
		load();
	}
}
void Ship::change() {
	Queue *p;
	p = now;
	now = op;
	op = p;
	time += cross;
}

int main()
{
	Queue left, right;
	Ship ship;
	int time[MAX], m;
	int T, t, i, x;
	char pos[16];

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d %d", &ship.limit, &ship.cross, &m);
		left.init();
		right.init();
		for(i = 0; i < m; i++) {
			scanf("%d %s", &x, pos);
			if(!strcmp(pos, "left")) {
				left.push(x, i);
			} else {
				right.push(x, i);
			}
		}
		ship.init(&left, &right);
		while(!left.isEmpty() || !right.isEmpty()) {
			ship.load();
			ship.change();
			for(i = 0; i < ship.n; i++) {
				time[ship.loaded[i]] = ship.time;
			}
		}
		if(t != 0) {
			putchar('\n');
		}
		for(i = 0; i < m; i++) {
			printf("%d\n", time[i]);
		}
	}
	
	return 0;
}