/* 2006 ACM ICPC 国内予選模擬練習会 E 問題ソース 基本はこの擬似コードが Builgind のコンストラクタ内の while 文で動いています while(キューが空でない){ e = イベントキューから最小を取り出す switch( e のイベントタイプ ){ case エレベータが出発 出発させる ElevatorRestrtEvent が担当 case エレベータが 1 階に到着 回収したデバイスの個数を追加 最後に回収した時刻更新 ElevatorArriveGroundFloorEvent が担当 case エレベータが 2階以上に到着 デバイスをエレベータに移す ElevatorArriveGroundFloorEvent が担当 if(階が空に)他のエレベータに通知 Building.floorDeviceDisappear が担当 case 階が焼失 FloorFireEvent が担当 他のエレベータに通知 Building.floorDeviceDisappear が担当 } } ここの debug のコメントアウトを外すとデバッグ出力を見ることができます while(!eventQueue.isEmpty()){ Event event = eventQueue.poll(); // event.debug(); if(!event.isValid(this))continue; // event.debug(); event.doEvent(this); } カプセル化等をがんばっているのですごいコードサイズになっていますが, 実際では適宜楽に書く工夫もすると,もっとコードサイズを抑えることが出来ると思います. */ import java.io.*; import java.util.*; class Main{ public static void main(String[] args)throws IOException{ Scanner s=new Scanner(System.in); while(true){ int floorNumber = s.nextInt(); int elevatorNumber = s.nextInt(); if(floorNumber == 0 && elevatorNumber == 0)break; new Building(floorNumber, elevatorNumber, s); } } } class Elevator{ private int capacity; private double velocity; private double stopTime; private int deviceNumber; private double height; private double localTime; private ElevatorArriveUpperFloorEvent event; Elevator(int c, double v, double st, double h){ capacity = c; velocity = v; stopTime = st; height = h; deviceNumber = 0; localTime = 0.0; event = null; } public double getVelocity(){ return(velocity); } public double getStopTime(){ return(stopTime); } public double getLocalTime(){ return(localTime); } public int getRestCapacity(){ return(capacity - deviceNumber); } public int getDeviceNumber(){ return(deviceNumber); } public void addDeviceNumber(int dn){ deviceNumber += dn; } public void setDeviceNumberZero(){ deviceNumber = 0; } public void setLocalTimeAndHeight(double lt, double h){ localTime = lt; height = h; event = null; } public void setLocalTimeAndMove(double lt){ double timeDiff = lt - localTime; double targetHeight = event.getWhichFloor(); double heightDiff = timeDiff * velocity; if(height < targetHeight){ height += heightDiff; } else{ height -= heightDiff; } localTime = lt; event = null; } public double getHeight(){ return(height); } public void setElevatorArriveUpperFloorEvent(ElevatorArriveUpperFloorEvent e){ event = e; } public ElevatorArriveUpperFloorEvent getElevatorArriveUpperFloorEvent(){ return(event); } } abstract class Event implements Comparable{ protected double eventTime; protected Event(double et){ eventTime = et; } public double getEventTime(){ return(eventTime); } public int compareTo(Event e){ if(eventTime > e.getEventTime())return(1); if(eventTime < e.getEventTime())return(-1); return(0); } abstract boolean isValid(Building b); abstract void doEvent(Building b); abstract void debug(); } class ElevatorArriveGroundFloorEvent extends Event{ private int whichElevator; ElevatorArriveGroundFloorEvent(double et, int we){ super(et); whichElevator = we; } public boolean isValid(Building b){ return(true); } public void debug(){ System.err.println("ElevatorArriveGroundFloorEvent t:" + eventTime + " e:" + whichElevator); } public void doEvent(Building b){ Elevator elevator = b.getElevator(whichElevator); int deviceNumber = elevator.getDeviceNumber(); double stopTime = elevator.getStopTime(); double nextEventTime = eventTime + stopTime; b.addSurviveDevice(deviceNumber, nextEventTime); elevator.setDeviceNumberZero(); elevator.setLocalTimeAndHeight(nextEventTime, 0.0); b.addEvent(new ElevatorRestartEvent(nextEventTime, whichElevator)); } } class ElevatorArriveUpperFloorEvent extends Event{ private int whichElevator; private int whichFloor; ElevatorArriveUpperFloorEvent(double et, int we, int wf){ super(et); whichElevator = we; whichFloor = wf; } public boolean isValid(Building b){ Elevator e = b.getElevator(whichElevator); return(e.getElevatorArriveUpperFloorEvent() == this); } public void debug(){ System.err.println("ElevatorArriveUpperFloorEvent t:" + eventTime + " e:" + whichElevator + " f:" + whichFloor); } public void doEvent(Building b){ Elevator elevator = b.getElevator(whichElevator); int moveDeviceNumber = Math.min(b.getDeviceNumber(whichFloor), elevator.getRestCapacity()); elevator.addDeviceNumber(moveDeviceNumber); b.subDeviceNumber(whichFloor, moveDeviceNumber); double stopTime = elevator.getStopTime(); double nextEventTime = eventTime + stopTime; elevator.setLocalTimeAndHeight(nextEventTime, (double)whichFloor); b.addEvent(new ElevatorRestartEvent(nextEventTime, whichElevator)); if(b.getDeviceNumber(whichFloor) == 0){ b.floorDeviceDisappear(eventTime, whichFloor); } } public int getWhichFloor(){ return(whichFloor); } } class ElevatorRestartEvent extends Event{ private int whichElevator; ElevatorRestartEvent(double et, int we){ super(et); whichElevator = we; } public boolean isValid(Building b){ return(true); } public void debug(){ System.err.println("ElevatorRestartEvent t:" + eventTime + " e:" + whichElevator); } public void doEvent(Building b){ Elevator elevator = b.getElevator(whichElevator); int targetFloor = -1; if(elevator.getRestCapacity() == 0){ targetFloor = 0; } else{ targetFloor = b.getSurviveDeviceMaxFloor(); if(targetFloor < 0 && elevator.getDeviceNumber() > 0){ targetFloor = 0; } } if(targetFloor >= 0){ double nextEventTime = eventTime + Math.abs(elevator.getHeight() - targetFloor) / elevator.getVelocity(); if(targetFloor == 0){ ElevatorArriveGroundFloorEvent elevatorArriveGroundFloorEvent = new ElevatorArriveGroundFloorEvent(nextEventTime, whichElevator); b.addEvent(elevatorArriveGroundFloorEvent); } else{ ElevatorArriveUpperFloorEvent elevatorArriveUpperFloorEvent = new ElevatorArriveUpperFloorEvent(nextEventTime, whichElevator, targetFloor); b.addEvent(elevatorArriveUpperFloorEvent); elevator.setElevatorArriveUpperFloorEvent(elevatorArriveUpperFloorEvent); } } } } class FloorFireEvent extends Event{ private int whichFloor; FloorFireEvent(double et, int wf){ super(et); whichFloor = wf; } public boolean isValid(Building b){ return(true); } public void debug(){ System.err.println("FloorFireEvent t:" + eventTime + " f:" + whichFloor); } public void doEvent(Building b){ b.setDeviceNumber(whichFloor, 0); b.floorDeviceDisappear(eventTime, whichFloor); } } class Building{ int floorNumber; int elevatorNumber; int[] floorDeviceNumber; Elevator[] elevator; PriorityQueue eventQueue; int surviveDeviceNumber; double lastSurviveDeviceArriveTime; Building(int fn, int en, Scanner s){ floorNumber = fn; elevatorNumber = en; double distance = s.nextDouble(); floorDeviceNumber = new int[floorNumber]; for(int i = 0; i < floorNumber; i++){ floorDeviceNumber[i] = s.nextInt(); } elevator = new Elevator[elevatorNumber]; for(int i = 0; i < elevatorNumber; i++){ elevator[i] = new Elevator(s.nextInt(), s.nextDouble() / distance, s.nextDouble(), (s.nextDouble() - 1.0)); } int fireStartLevel = s.nextInt() - 1; double fireTime = s.nextDouble(); double fireUpTime = s.nextDouble(); double fireDownTime = s.nextDouble(); eventQueue = new PriorityQueue(); surviveDeviceNumber = floorDeviceNumber[0]; lastSurviveDeviceArriveTime = 0.0; for(int level = fireStartLevel; level > 0; level--){ addEvent(new FloorFireEvent(fireTime + fireDownTime * (fireStartLevel - level), level)); } for(int level = fireStartLevel + 1; level < floorNumber; level++){ addEvent(new FloorFireEvent(fireTime + fireUpTime * (level - fireStartLevel), level)); } for(int i = 0; i < elevatorNumber; i++){ addEvent(new ElevatorRestartEvent(0.0, i)); } while(!eventQueue.isEmpty()){ Event event = eventQueue.poll(); // event.debug(); if(!event.isValid(this))continue; // event.debug(); event.doEvent(this); } System.out.print(surviveDeviceNumber); System.out.print(" "); System.out.println(lastSurviveDeviceArriveTime); } public int getDeviceNumber(int level){ return(floorDeviceNumber[level]); } public void setDeviceNumber(int level, int deviceNumber){ floorDeviceNumber[level] = deviceNumber; } public void subDeviceNumber(int level, int deviceNumber){ floorDeviceNumber[level] -= deviceNumber; } public Elevator getElevator(int whichElevator){ return(elevator[whichElevator]); } public void floorDeviceDisappear(double eventTime, int level){ for(int i = 0; i < elevatorNumber; i++){ Elevator e = elevator[i]; ElevatorArriveUpperFloorEvent eae = e.getElevatorArriveUpperFloorEvent(); if(eae != null && eae.getWhichFloor() == level){ e.setLocalTimeAndMove(eventTime); addEvent(new ElevatorRestartEvent(eventTime, i)); } } } public void addSurviveDevice(int deviceNumber, double deviceArriveTime){ surviveDeviceNumber += deviceNumber; lastSurviveDeviceArriveTime = Math.max(lastSurviveDeviceArriveTime, deviceArriveTime); } public void addEvent(Event event){ eventQueue.add(event); } public int getSurviveDeviceMaxFloor(){ for(int level = floorNumber - 1; level > 0; level--){ if(floorDeviceNumber[level] > 0)return(level); } return(-1); } }