2343.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2343 on 2006-09-09 at 10:30:30 */ 
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int N = 128;
 
class Student {
public:
	int n, qb[N], id;
	void make();
	int request() { return qb[id++]; }
};
void Student::make() {
	scanf("%d", &n); id = 0;
	for(int i = 0; i < n; i++) scanf("%d", &qb[i]);
}
 
Student s[N];
int fb[N], fp[N];
 
int main()
{
	int m, n, c;
	
	while(scanf("%d %d %d", &m, &c, &n) != EOF && !(m == 0 && n == 0 && c == 0)) {
		int cost = 0, bp[N], nb[N] = { 0 };
		for(int i = 0; i < n; i++) s[i].make();
		for(int i = 0; i < N; i++) bp[i] = m+1;
		nb[m+1] = N;
		int rsn = n;
		memset(fb, -1, sizeof(fb));
		for(int i = 0, j = 0; rsn != 0; i = (i+1)%n, j++) {
			if(s[i].id == s[i].n) continue;
			int qN = s[i].request();
			if(s[i].id == s[i].n) rsn--;
			cost += bp[qN]; nb[bp[qN]]--;
			if(bp[qN] == 1)
				for(int i = 0; i < c; i++)
					if(fb[i] == qN) { fb[i] = -1; break; }
			bool pos = false;
			int pj, pt = 100000;
			for(int i = 0; i < c; i++)
				if(fb[i] == -1) { fb[i] = qN; fp[i] = j; pos = true; break; }
				else if(pt > fp[i]) { pt = fp[i]; pj = i; }
			if(pos) { cost++; bp[qN] = 1; continue; }
			bool ptb = false;
			cost++;
			for(int i = 2; i <= m; i++)
				if(nb[i] != c) { nb[i]++; bp[qN] = i; cost += i; ptb = true; break; }
			if(!ptb) { bp[qN] = m+1; cost += m+1; nb[m+1]++; }
			ptb = false;
			for(int i = 2; i <= m; i++)
				if(nb[i] != c) { nb[i]++; bp[fb[pj]] = i; cost += i; ptb = true; break; }
			if(!ptb) { bp[fb[pj]] = m+1; cost += m+1; nb[m+1]++; }
			cost += bp[qN]; nb[bp[qN]]--;
			cost++; fb[pj] = qN; fp[pj] = j; bp[qN] = 1;
		}
		printf("%d\n", cost);
	}
	
	return 0;
}