AOJ1219 Pump up Batteries - nanikakaのAOJ航海日誌

概要

N人の警備員がいる。彼らはそれぞれPCで仕事をする。しかしバッテリーが貧弱なので充電器で充電する必要があるが、充電器が1つしかない。彼らは、仕事をする時間s、充電する時間tの時間がサイクルになって決まっている。sだけ仕事した後、充電器を使ってtの間充電する。充電器を使おうとしたとき、既にほかの人に使われていた場合はその人の充電が終わるまで待たなければならない。また、同時に充電器を使おうとした場合、IDの若い人が先に使うものとする。
このシミュレーションを時間Tだけ行ったとき、充電器を使うために待つ時間のN人の合計を答えよ。
N <= 100
T <= 10080
警備員のサイクルの長さ <= 50

解法

T時間のシミュレートを単位時間ずつ行っていきます。
このとき、N人それぞれについて、サイクルの何番目にいるか、その時間の残り、充電待ちかという情報を管理します。
そして、充電器の待ち行列を管理します。
自分の単位時間におけるシミュレートアルゴリズムとしては、
1.N人の中で充電待ちでない人を探す
　その人の残り時間が0ならば仕事をする時間が終了しているので待ち行列にその人を突っ込む
　そうでないならば仕事の残り時間を1減らす
2.待ち行列が空なら1に戻る
3.N人の中で充電待ちの人を探す
　待ち行列の先頭の人ならばその人の充電残り時間を1減らす。充電残り時間が0になったら、待ち行列から取り除き、次のサイクルに移行する
　先頭の人でないならば、待たされるので待ち時間のカウントを増やす
以上のような感じになっています（ソースコードを読み返した感じでは）
待ち行列において優先順位はまず、充電器を使おうとした時間が早い人、次いでIDが若い人の順番です。

ソース

import java.util.PriorityQueue;
import java.util.Scanner;

//Pump up Batteries
public class AOJ1219 {

	class E implements Comparable<E>{
		int id, t;
		public E(int id, int t) {
			this.id = id;
			this.t = t;
		}
		public int compareTo(E o) {
			return t==o.t?id-o.id:t-o.t;
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt();
			int T = sc.nextInt();
			if((n|T)==0)break;
			int[][] com = new int[n][50];
			int[][] ch = new int[n][50];
			int[] k = new int[n];
			for(int i=0;i<n;i++){
				for(;;){
					int x = sc.nextInt();
					if(x==0)break;
					com[i][k[i]] = x;
					ch[i][k[i]] = sc.nextInt();
					k[i]++;
				}
			}
			int res = 0;
			boolean[] wait = new boolean[n];
			int[] val = new int[n];
			for(int i=0;i<n;i++)val[i] = com[i][0];
			int[] p = new int[n];
			PriorityQueue<E> q = new PriorityQueue<E>();
			for(int t=0;t<T;t++){
				for(int i=0;i<n;i++){
					if(wait[i])continue;
					if(val[i]==0){
						wait[i] = true;
						val[i] = ch[i][p[i]];
						q.add(new E(i, t));
					}
					else val[i]--;
				}
				if(q.isEmpty())continue;
				E e = q.peek();
				for(int i=0;i<n;i++){
					if(e.id==i){
						val[i]--;
						if(val[i]==0){
							q.poll();
							p[i] = (p[i]+1)%k[i];
							val[i] = com[i][p[i]];
							wait[i] = false;
						}
					}
					else if(wait[i])res++;
				}
			}
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1219().run();
	}
}