AOJ2059 Restaurant

問題リンク Restaurant

• 概要

レストランのコックの動きをシミュレーションせよ。
コックは1人しかいない。レストランにはN個のメニューがある。メニュー i を調理するのにtiの時間がかかる。
注文は先着したものが優先的に処理される。コックは作らなければならない注文のリストの内、調理に最も時間がかかるものから料理する。それが複数個ある場合、メニューリストで最初にあらわれるものを料理する。1つ分の注文リストに登場する料理が全て完成したら即座に運ばれる。運ばれる時間は無視してよい。
料理を作ろうとしたとき、その時点の時刻を含めて、受注した料理リストを眺め、今作ろうとしている料理が何個あるかを見る。そして、それが複数個ある場合、コックは一度に複数個同じ料理を作る。調理に掛かる時間は1個でも複数個でも変わらない。但し、メニュー i を同時に作れる個数は最大 Limit_i 個までである。必要な料理の数がLimit_iより大きい場合、コックは作れるだけ料理を作る。
M個の注文リストが与えられる。j番目の注文は時刻Tjに発注され、kj個の料理からなる。kj個の各料理の中には同じ料理が複数回頼まれることもある。同じ時刻に2つ以上の注文が発生することはない。また、メニューリストに登場する料理以外のものが注文されることはない。
j番目に注文した料理がいつ運ばれてくるのかをリストアップせよ。
1 <= N <= 20
1 <= M <= 100
1 <= Limit_i <= 10
1 <= ti <= 10^3
1 <= Tj <= 10^7
1 <= Kj <= 10

• 解法

コックがある時刻tに作る料理は、まとめると
・時刻t以内で受注した注文の中で
・まだ料理していないものの中で
・注文を受けたのが最も速い物の中で
・最も料理に時間がかかるものの中で
・最も早くメニューリストに登場する料理 i を Limit_i個作る
となります。料理 i を必要とされる数より多く作ってもシミュレート結果は変わらないので作れるだけ作ります。この料理を順に注文リストに割り当てます。割り当てた結果全ての料理が揃った注文があったら、t + tiにその注文の料理が揃ったことになります。

• ソース

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

//Restaurant
public class AOJ2059 {

	class R implements Comparable<R>{
		int oid, id;
		public R(int oid, int id) {
			this.oid = oid;
			this.id = id;
		}
		public int compareTo(R o) {
			return oid!=o.oid?oid-o.oid:p[id]!=p[o.id]?p[o.id]-p[id]:id-o.id;
		}
	}

	int n, m;
	int[] p, limit, T, K, res;
	Map<String, Integer> ref;
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		for(boolean head = true;;head = false){
			n = sc.nextInt(); m = sc.nextInt();
			if((n|m)==0)break;
			if(!head)System.out.println();
			ref = new HashMap<String, Integer>();
			limit = new int[n];
			p = new int[n];
			T = new int[m];
			K = new int[m];
			for(int i=0;i<n;i++){
				ref.put(sc.next(), i);
				limit[i] = sc.nextInt();
				p[i] = sc.nextInt();
			}
			List<R>[] l = new List[m];
			for(int i=0;i<m;i++){
				l[i] = new ArrayList<R>();
				T[i] = sc.nextInt();
				K[i] = sc.nextInt();
				for(int j=0;j<K[i];j++)l[i].add(new R(i, ref.get(sc.next())));
			}
			res = new int[m];
			int f = 0, t = 0;
			LinkedList<R> list = new LinkedList<R>();
			while(f<m||!list.isEmpty()){
				while(f<m&&T[f]<=t){
					list.addAll(l[f++]);
				}
				if(list.isEmpty()&&f<m){
					t = T[f]; list.addAll(l[f++]);
				}
				Collections.sort(list);
				R r = list.get(0);
				t += p[r.id];
				int L = limit[r.id];
				for(int i=0;i<list.size()&&0<L;i++){
					R d = list.get(i);
					if(d.id!=r.id)continue;
					--L;
					if(--K[d.oid]==0)res[d.oid] = t;
					list.remove(i--);
				}
			}
			for(int r:res)System.out.println(r);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2059().run();
	}
}