Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Jun 22nd, 2012  |  syntax: Java  |  size: 2.81 KB  |  hits: 20  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1.  
  2. import java.io.*;
  3. import java.util.*;
  4.  
  5. class Job implements Comparable<Job> {
  6.  
  7.     int i;
  8.     long t, d;
  9.  
  10.     Job(int i, long t, long d) {
  11.         this.i = i;
  12.         this.t = t;
  13.         this.d = d;
  14.     }
  15.  
  16.     @Override
  17.     public int compareTo(Job arg0) {
  18.         if (d != arg0.d) {
  19.             return new Long(d).compareTo(arg0.d);
  20.         } else {
  21.                 if (t != arg0.t) {
  22.                         return new Long(t).compareTo(arg0.t);
  23.                 } else {
  24.                         return new Integer(i).compareTo(arg0.i);
  25.                 }
  26.         }
  27.     }
  28.  
  29.     public String toString() {
  30.         return "(" + i + ", " + t + ", " + d + ")";
  31.     }
  32. }
  33.  
  34. class CompareByTimeComparator implements Comparator<Job> {
  35.  
  36.     @Override
  37.     public int compare(Job arg0, Job arg1) {
  38.         if (arg0.t != arg1.t) {
  39.                 return new Long(arg0.t).compareTo(arg1.t);
  40.         } else {
  41.                 return new Integer(arg0.i).compareTo(arg1.i);
  42.         }
  43.     }
  44. }
  45.  
  46. public class p1sumuProblem {
  47.  
  48.     public static void main(String[] args) throws IOException {
  49.         new p1sumuProblem().run();
  50.     }
  51.  
  52.     TreeSet<Job> jobs;
  53.     long[] b;
  54.  
  55.     int solve() {
  56.         TreeSet<Job> result = new TreeSet<Job>();
  57.         TreeSet<Job> s = new TreeSet<Job>(new CompareByTimeComparator());
  58.         b = new long[jobs.size()];
  59.         int time = 0;
  60.  
  61.         for (Job job : jobs) {
  62.             s.add(job);
  63.             result.add(job);            
  64.             time += job.t;
  65.  
  66.             if (time > job.d) {
  67.                 Job pMax = s.pollLast();
  68.                 result.remove(pMax);                
  69.                 time -= pMax.t;
  70.             }
  71.         }
  72.  
  73.        
  74.         Arrays.fill(b, -1);
  75.         time = 0;
  76.         for (Job job : result) {
  77.             b[job.i] = time;
  78.             time += job.t;
  79.         }
  80.  
  81.         return result.size();
  82.     }
  83.  
  84.     void run() throws IOException {
  85.         br = new BufferedReader(new FileReader("p1sumu.in"));
  86.         pw = new PrintWriter("p1sumu.out");
  87.  
  88.         int n = nextInt();
  89.         jobs = new TreeSet<Job>();
  90.  
  91.         for (int i = 0; i < n; i++) {
  92.             jobs.add(new Job(i, nextLong(), nextLong()));
  93.         }      
  94.  
  95.         int result = solve();
  96.  
  97.         pw.println(result);
  98.         for (long l : b) {
  99.             pw.print(l + " ");
  100.         }
  101.  
  102.         pw.close();
  103.     }
  104.  
  105.     private BufferedReader br;
  106.     private StringTokenizer st;
  107.     private PrintWriter pw;
  108.  
  109.     private String next() throws IOException {
  110.         while (st == null || !st.hasMoreTokens()) {
  111.             st = new StringTokenizer(br.readLine());
  112.         }
  113.  
  114.         return st.nextToken();
  115.     }
  116.  
  117.     private int nextInt() throws IOException {
  118.         return Integer.parseInt(next());
  119.     }
  120.  
  121.     private long nextLong() throws IOException {
  122.         return Long.parseLong(next());
  123.     }
  124. }
create a new version of this paste RAW Paste Data