Crazy

Black Friday

Dec 19th, 2017
365
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.46 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Scanner;
  3.  
  4. class Heap<E extends Comparable<E>> {
  5.     private E[] elements;
  6.  
  7.     public Heap(int size) {
  8.         this.elements = (E[]) new Comparable[size];
  9.     }
  10.  
  11.     int getParent(int i) {
  12.         return (i + 1) / 2 - 1;
  13.     }
  14.  
  15.     public E getAt(int i) {
  16.         return this.elements[i];
  17.     }
  18.  
  19.     int getLeft(int i) {
  20.         return (i + 1) * 2 - 1;
  21.     }
  22.  
  23.     int getRight(int i) {
  24.         return (i + 1) * 2;
  25.     }
  26.  
  27.     void setElement(int index, E elem) {
  28.         this.elements[index] = elem;
  29.     }
  30.  
  31.     void swap(int i, int j) {
  32.         E tmp = this.elements[i];
  33.         this.elements[i] = this.elements[j];
  34.         this.elements[j] = tmp;
  35.     }
  36.  
  37.     void adjust(int i, int n) {
  38.         while(true) {
  39.             if (i < n) {
  40.                 int left = this.getLeft(i);
  41.                 int right = this.getRight(i);
  42.                 int largest = i;
  43.                 if (left < n&&this.elements[left].compareTo(this.elements[i]) > 0) {
  44.                     largest = left;
  45.                 }
  46.  
  47.                 if (right < n && this.elements[right].compareTo(this.elements[largest]) > 0) {
  48.                     largest = right;
  49.                 }
  50.  
  51.                 if (largest != i) {
  52.                     this.swap(i, largest);
  53.                     i = largest;
  54.                     continue;
  55.                 }
  56.             }
  57.  
  58.             return;
  59.         }
  60.     }
  61.  
  62.     void buildHeap() {
  63.         for(int i = this.elements.length / 2 - 1; i >= 0; --i) {
  64.             this.adjust(i, this.elements.length);
  65.         }
  66.  
  67.     }
  68.  
  69.     public void heapSort() {
  70.         this.buildHeap();
  71.  
  72.         for(int i = this.elements.length - 1; i > 0; --i) {
  73.             this.swap(0, i);
  74.             this.adjust(0, i);
  75.         }
  76.  
  77.     }
  78. }
  79.  
  80. class Entry implements Comparable<Entry> {
  81.     protected int vlez;
  82.     protected int prestoj;
  83.  
  84.     public Entry(int v, int p) {
  85.         this.vlez = v;
  86.         this.prestoj = p;
  87.     }
  88.  
  89.     public int vkupno() {
  90.         return this.vlez + this.prestoj;
  91.     }
  92.  
  93.     public int compareTo(Entry e) {
  94.         if (this.vlez > e.vlez) {
  95.             return 1;
  96.         } else {
  97.             return this.vlez < e.vlez ? -1 : 0;
  98.         }
  99.     }
  100. }
  101.  
  102. public class BlackFriday {
  103.     public BlackFriday() {
  104.     }
  105.  
  106.     public static void main(String[] args) throws Exception {
  107.         Scanner br = new Scanner(System.in);
  108.         int N = Integer.parseInt(br.nextLine());
  109.         Heap<Entry> heapDrvo = new Heap(N);
  110.  
  111.         for(int i = 0; i < N; ++i) {
  112.             String s = br.nextLine();
  113.             String[] pom = s.split(" ");
  114.             String[] cas = pom[0].split(":");
  115.             int vlez = Integer.parseInt(cas[0]) * 60 + Integer.parseInt(cas[1]);
  116.             int prestoj = Integer.parseInt(pom[1]);
  117.             Entry nov = new Entry(vlez, prestoj);
  118.             heapDrvo.setElement(i, nov);
  119.         }
  120.  
  121.         heapDrvo.heapSort();
  122.         ArrayList<Entry> lista = new ArrayList(0);
  123.         int max = 0;
  124.  
  125.         for(int i = 0; i < N; ++i) {
  126.             for(int j = 0; j < lista.size(); ++j) {
  127.                 if (((Entry)lista.get(j)).vkupno() < ((Entry)heapDrvo.getAt(i)).vlez) {
  128.                     lista.remove(j);
  129.                 }
  130.             }
  131.  
  132.             lista.add((Entry)heapDrvo.getAt(i));
  133.             if (lista.size() > max) {
  134.                 max = lista.size();
  135.             }
  136.         }
  137.  
  138.         System.out.println(max);
  139.         br.close();
  140.     }
  141. }
Advertisement
Add Comment
Please, Sign In to add comment