1837.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1837 on 2006-08-25 at 00:32:10 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1 << 20;
const int B = 1024;

int truck[N], store[N], nxt[N], head[N];

class App {
public:
	int t, o;
	App(int ct, int co) : t(ct), o(co) {}
};

class Heap {
private:
	void siftDown(int);
	void siftUp(int);
public:
	int size, d[B], o[B], p[N];
	void clear() { size = 0; memset(p, -1, sizeof(p)); }
	bool exist(int to) const { return p[to] != -1; }
	App top() const { return App(d[0], o[0]); }
	void push(int, int);
	void pop();
};
void Heap::push(int m, int v) {
	int idx = size;
	if(p[m] == -1) { o[size] = m; p[m] = idx = size++; }
	else if(d[p[m]] >= v) return;
	else idx = p[m];
	d[idx] = v; siftUp(idx);
}
void Heap::pop() {
	p[o[0]] = -1;
	--size;
	if(size != 0) {
		d[0] = d[size]; o[0] = o[size]; p[o[0]] = 0;
		siftDown(0);
	}
	d[size] = -1;
}
void Heap::siftDown(int k) {
	int i, m, dk = d[k], ok = o[k];
	for(i = k; i < size; i = m) {
		if(2*i+1 > size) break;
		m = 2*i+1;
		if(m+1 < size && d[m] < d[m+1]) m++;
		if(dk > d[m]) break;
		d[i] = d[m]; o[i] = o[m]; p[o[i]] = i;
	}
	d[i] = dk; o[i] = ok; p[ok] = i;
}
void Heap::siftUp(int k) {
	int i, m, dk = d[k], ok = o[k];
	for(i = k; i > 0; i = m) {
		m = (i-1)/2;
		if(d[m] > dk) break;
		d[i] = d[m]; o[i] = o[m]; p[o[i]] = i;
	}
	d[i] = dk; o[i] = ok; p[ok] = i;
}

Heap Q;

int main()
{
	int T, b, g, n;

	scanf("%d", &T);
	for(int t = 1; t <= T; t++) {
		if(t != 1) putchar('\n');
		scanf("%d %d %d", &b, &g, &n);
		memset(head, -1, sizeof(int)*g);
		for(int i = 0; i < n; i++) 
			{ scanf("%d", &truck[i]); truck[i]--; }
		for(int i = n-1; i >= 0; i--) {
			if(head[truck[i]] == -1) nxt[i] = N;
			else nxt[i] = head[truck[i]];
			head[truck[i]] = i;
		}
		Q.clear();
		printf("Case %d:\n", t);
		for(int i = 0, ck = 0; i < n; i++) {
			int to = truck[i];
			if(Q.exist(to)) printf("NO ACTION\n");
			else if(ck < b) {
				printf("LOAD %d %d\n", ck+1, to+1);
				store[to] = ck++;
			} else {
				App p = Q.top(); Q.pop();
				int ps = store[p.o];
				printf("LOAD %d %d\n", ps+1, to+1);
				store[to] = ps;
			}
			Q.push(to, nxt[i]);
		}
	}
	
	return 0;
}