제출 #464276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
464276		PikaChu999	Job Scheduling (CEOI12_jobs)	Java	컴파일 에러	0 ms	0 KiB

jobs

/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4 
*/
import java.util.*;
import java.io.*;

public class Main {
  public static long numDays;
  public static long maxDelay; 
  public static int numRequests;
  public static Request[] requests;
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer details = new StringTokenizer(br.readLine());
    numDays = Long.parseLong(details.nextToken());
    maxDelay = Long.parseLong(details.nextToken());
    numRequests = Integer.parseInt(details.nextToken());

    requests = new Request[numRequests];
    StringTokenizer r = new StringTokenizer(br.readLine());
    for(int x = 0; x < numRequests; x++) requests[x] = new Request(x, Long.parseLong(r.nextToken()));
    Arrays.sort(requests);
    //System.out.println(Arrays.toString(requests));

    //output is formatted by requests + " " + 0
    long min = 0;
    long max = 10000000;

    while(min < max){
      long mid = (min + max)/2;
      if(works(mid)){
        max = mid;
      }
      else min = mid + 1;
    }

    generate(max);

    br.close();
  }
  public static boolean works(long numMachines){
    PriorityQueue<Request> delayed = new PriorityQueue<Request>();
    long currentDay = 0;
    int requestInd = 0;
    long available = numMachines;
    while(currentDay <= numDays){
      //System.out.println(currentDay + " " + delayed + " " + requestInd);
      //even on days where there are no new requests one can work on the delayed ones
      available = numMachines; 
      while(!delayed.isEmpty() && available > 0){
        available--; 
        Request cur = delayed.poll();
        if(currentDay - cur.day > maxDelay) return false; 
      }
      while(requestInd < numRequests && requests[requestInd].day == currentDay){
        if(available > 0){
          available--;
          requestInd++;
        }
        else{
          delayed.add(requests[requestInd]);
          requestInd++;
        }
      }
      currentDay++;
    }
    return requestInd >= numRequests - 1;
  }
  public static void generate(long numMachines){
    System.out.println(numMachines);
    PriorityQueue<Request> delayed = new PriorityQueue<Request>();
    long currentDay = 0;
    int requestInd = 0;
    long available = numMachines;
    while(currentDay <= numDays){
      //System.out.println(currentDay + " " + delayed + " " + requestInd);
      //even on days where there are no new requests one can work on the delayed ones
      ArrayList<Request> processed = new ArrayList<Request>();
      available = numMachines; 
      while(!delayed.isEmpty() && available > 0){
        available--; 
        processed.add(delayed.poll());
      }
      while(requestInd < numRequests && requests[requestInd].day == currentDay){
        if(available > 0){
          available--;
          processed.add(requests[requestInd]);
          requestInd++;
        }
        else{
          delayed.add(requests[requestInd]);
          requestInd++;
        }
      }
      currentDay++;
      String ret = "";
      for(Request r : processed) ret += r.toString() + " ";
      System.out.println(ret + "0");
    }
  }
}
class Request implements Comparable<Request>{
  long day; 
  int id; 
  public Request(int i, long d){
    day = d;
    id = i;
  }
  public int compareTo(Request r){
    if(r.day < day) return 1;
    else if(r.day > day) return -1;
    return id - r.id;
  }
  public String toString(){
    return String.valueOf(id);
  }
}

컴파일 시 표준 에러 (stderr) 메시지

jobs.java:8: error: class Main is public, should be declared in a file named Main.java
public class Main {
       ^
1 error