1258-Book Replacement

問題概要

(読解系実装問題なので省略)

解法

listを用いてシミュレートする．

実装(C++)

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <fstream>
using namespace std;

typedef long long int lli;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)

#define dout(...) printf(__VA_ARGS__);fflush(stdout);
int n,m,c;
struct Book{
	int ID;
	int last_access;
};
list<Book> shelf[101];
queue<int> students;
queue<int> students_req[101];
//本を検索しみつかったら持っていく
int search(int ID){
	REP(i,m){
		FOR(it,shelf[i]){
			if(it->ID==ID){
				shelf[i].erase(it++);//いらないので消す
				return i;
			}
		}
	}
	return m;
}
int search_free(){
	REP(i,m){
		if(shelf[i].size()<(unsigned int)c)return i;
	}
	return m;
}
int main(){
	for(;;){
		cin>>m>>c>>n;
		if(m==0&&n==0&&c==0)break;
		students=queue<int>();
		REP(i,n){
			int k;
			cin>>k;
			students_req[i]=queue<int>();
			REP(j,k){
				int t;cin>>t;
				students_req[i].push(t);
			}
			students.push(i);
		}
		REP(i,m+1){
			shelf[i].clear();
		}
		int time=0;
		while(!students.empty()){
			int next=students_req[students.front()].front();
			students_req[students.front()].pop();
			if(!students_req[students.front()].empty()){
				students.push(students.front());
			}
			students.pop();

			time+=search(next)+1;
			//本を戻す
			if((int)shelf[0].size()<c){
				shelf[0].push_back((Book){next,time});
				time+=1;
			}else{
				int tmp=search_free();
				if(tmp<m)shelf[tmp].push_back((Book){next,time});
				time+=tmp+1; //D1に戻る
				int latest_time=99999999;
				list<Book>::iterator rv;
				FOR(it,shelf[0]){
					if(it->last_access<latest_time){
						latest_time=it->last_access;
						rv=it;
					}
				}
				//一番近い空いている本棚に移動する
				tmp=search_free();
				if(tmp<m)shelf[tmp].push_back(*rv);
				shelf[0].erase(rv++);
				time+=1;
				time+=tmp+1;

				//tmp本棚から1に移動する
				time+=1+search(next);
				shelf[0].push_back((Book){next,time});
				time+=1;
			}
		}
		cout<<time<<endl;
	}
	return 0;
}