1611.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1611 on 2006-03-03 at 18:21:22 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int ADRS_MAX = 65536;
const int B_MAX = 128;
const int N_MAX = 1024;

class Cache {
public:
	int size, bn, accTime;
	int bit[B_MAX], used[B_MAX], issue[ADRS_MAX];
	void make();
	void memory();
	void insert(int, int);
};
void Cache::make() {
	scanf("%d %d %d", &size, &bn, &accTime);
	bn /= size;
	memset(issue, -1, sizeof(issue)); memset(used, -1, sizeof(used));
}
void Cache::memory() {
	memset(issue, 0, sizeof(issue));
	scanf("%d", &accTime);
}
void Cache::insert(int cb, int turn) {
	if(issue[cb] != -1) { used[issue[cb]] = turn; return; }
	cb = cb / size * size;
	int i, best = N_MAX, bo;
	for(i = 0; i < bn; i++) {
		if(best > used[i]) best = used[i], bo = i;
		if(best == -1) break;
	}
	if(best != -1) for(i = 0; i < size; i++) issue[i+bit[bo]] = -1;
	for(i = 0; i < size; i++) issue[i+cb] = bo;
	bit[bo] = cb; used[bo] = turn;
}

int main()
{
	Cache cache[4];
	int i, j, t, cn;
	
	for(t = 1; scanf("%d", &cn) != EOF && cn != 0; t++) {
		int total = 0, n;
		for(i = 0; i < cn; i++) cache[i].make();
		cache[cn++].memory();
		scanf("%d", &n);
		for(i = 0; i < n; i++) {
			int need, isn; scanf("%d", &need);
			for(isn = 0; isn < cn; isn++)
				if(cache[isn].issue[need] != -1) break;
			for(j = isn; j >= 0; j--) {
				total += cache[j].accTime;
				cache[j].insert(need, i);
			}
		}
		printf("Case %d: total time = %d nanoseconds\n", t, total);
	}
	
	return 0;
}