AOJ1258 Book Replacement - nanikakaのAOJ航海日誌

概要

図書館の書庫にはM個の台と1つの棚がある。台には入口から近い順にD1〜DMと番号がついている。台には一度にC冊の本が置ける。
図書館の司書は客からリクエストを受け取るたびに、リクエストされた本を書庫から取ってきて、貸し出したのち、書庫に戻す。
N人の客が列になってリクエストを出す。各客はki個のリクエストがあるが、一度にリクエストできるのは1冊のため、一度リクエストをしたら列の最後尾に並ぶ。N人の客の全てのリクエストを処理するときの司書のコストを答えよ。
司書は「本を取る」「本を置く」毎にコストがかかる。コストの量はその作業を行った入口からの遠さである。つまり、D1なら1、DMならM、棚ならばM+1である。
司書は最初にリクエストされた本を入口に近い台から探す。見つからなければ棚から取る。
次に司書は貸し出した本を以下のように台に戻す。
D1の台に空きがある場合
　本をD1の台に置く
D1が一杯の場合
　入口から一番近い位置にある、空きがある台に本を置く。なければ棚に置く。
　D1に置いてある本の中で、最後に貸し出してから最も時間が経っている本を取り出す。
　取り出した本を、入口から一番近い位置にある、空きがある台に置く。なければ棚に置く。
　リクエストを受けた本を再び取り、D1に置く。
1 <= M <= 10
1 <= C <= 30
1 <= N <= 100
1 <= ki <= 50
本の番号 <= 100

解法

単なるシミュレート問題です。
D1の台はキューを使えば「最も時間が経っている本を取り出す」処理が楽になります。他の台はSetだろうがListだろうがデータ構造は何でもいいと思います。棚に関してはデータを持つ必要はないでしょう。

ソース

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

//Book Replacement
public class AOJ1258 {

	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int m = sc.nextInt(), c = sc.nextInt(), n = sc.nextInt();
			if((m|c|n)==0)break;
			int[] k = new int[n];
			int[][] req = new int[n][50];
			for(int i=0;i<n;i++){
				k[i] = sc.nextInt();
				for(int j=0;j<k[i];j++)req[i][j]=sc.nextInt();
			}
			Queue<Integer> D1 = new LinkedList<Integer>();
			Set<Integer>[] d = new Set[m+1];
			for(int i=2;i<=m;i++)d[i]=new HashSet<Integer>();
			int res = 0;
			for(int j=0;j<50;j++)for(int i=0;i<n;i++){
				if(k[i]<=j)continue;
				int r = req[i][j];
				if(D1.contains(r)){
					res += 2; D1.remove(r); D1.add(r);
					continue;
				}
				boolean shelf = true;
				for(int a=2;a<=m;a++){
					if(d[a].contains(r)){
						shelf = false;
						d[a].remove(r); res+=a;
						break;
					}
				}
				if(shelf)res+=m+1;
				if(D1.size()<c){
					res+=1; D1.add(r);
					continue;
				}
				int pos = -1;
				for(int a=2;a<=m;a++){
					if(d[a].size()<c){
						pos = a; res+=a; d[a].add(r); break;
					}
				}
				if(pos==-1)res+=m+1;
				int old = D1.poll();
				res+=1;
				shelf = true;
				for(int a=2;a<=m;a++){
					if(d[a].size()<c){
						shelf = false;
						d[a].add(old); res+=a;
						break;
					}
				}
				if(shelf)res+=m+1;
				if(pos!=-1){
					d[pos].remove(r); res+=pos;
				}
				else res+=m+1;
				D1.add(r); res+=1;
			}
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1258().run();
	}
}