ababup1192
2/15/2015 - 10:50 AM

Elementary data structures - Queue http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_B

import scala.collection.mutable.ArrayBuffer
import scala.io.StdIn


object Main extends App {

  val Array(n, quantum) = StdIn.readLine().split(" ").map(_.toInt)
  val queue = Queue(quantum)

  Iterator.continually(StdIn.readLine()).takeWhile(_ != null).foreach {
    _.split(" ") match {
      case Array(pName: String, time: String) => queue.enqueue(Data(pName, time.toInt))
    }
  }

  Iterator.continually {
    val data = queue.dequeue()
    if (data.time == 0) {
      println(s"${data.pName} ${queue.currentTime}")
    }
    queue.isEmpty
  } forall (!_)
}

case class Queue(quantum: Int) {
  var currentTime = 0
  private[this] val queue = ArrayBuffer.empty[Data]

  def enqueue(data: Data): Unit = {
    queue.append(data)
  }

  def dequeue(): Data = {
    val data = queue.remove(0)
    val time = Math.min(quantum, data.time)
    currentTime += time
    val newData = Data(data.pName, data.time - time)
    if (newData.time != 0) {
      queue.append(newData)
    }
    newData
  }

  def isEmpty: Boolean = {
    queue.isEmpty
  }
}

case class Data(pName: String, time: Int)
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static int quantum;
    public static int currentTime = 0;
    public Main() {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int quantum = scan.nextInt();

        Queue queue = new Queue(100000 + n);
        this.quantum = quantum;

        while(scan.hasNext()){
            String pName = scan.next();
            int time = scan.nextInt();
            queue.enqueue(new Data(pName, time));
        }
        while(!queue.isEmpty()){
            Data data = queue.dequeue();
            if(data.time == 0){
                System.out.println(data.pName + " " + currentTime);
            }
        }
    }

    public static void main(String[] args) {
        new Main();
    }

    private class Queue{
        private int head = 0;
        private int tail = 0;
        private Data queue[];

        public Queue(int size){
            queue = new Data[size*2];
        }

        public void enqueue(Data data){
            queue[tail++] = data;
        }

        public Data dequeue(){
            Data data = queue[head++];
            int time = expendedTime(data);
            if(data.time != 0){
                enqueue(data);
            }
            currentTime += time;
            return data;
        }

        public int expendedTime(Data data){
            int time;
            if(data.time > quantum){
                time = quantum;
                data.time -= quantum;
            }else{
                time = data.time;
                data.time = 0;
            }
            return time;
        }

        public boolean isEmpty(){
            return head == tail;
        }

    }

    private class Data{
        public String pName;
        public int time;

        public Data(String pName, int time){
            this.pName = pName;
            this.time = time;
        }
    }
}