Airport (218B) – Codeforces Round #134 (Div. 2)

http://codeforces.com/problemset/problem/218/B

This is a very easy problem to solve given that you know what data structure to use!

The data structure you need here is a heap. A heap is a tree like data structure which offers O(log(n)) inserts and removes and it also keeps the smallest or biggest element at the head.

Here is my code for solving the question:
PriorityQueue<> is the heap like data structure in java. It is a min-heap by default so I used some trickery to quickly convert it into a max-heap.

import java.util.*;

public class B {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int[] seats = new int[m];
    for (int i = 0; i < seats.length; i++) {
      seats[i] = sc.nextInt();
    }
    sc.close();

    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>();
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
    for (int i = 0; i < seats.length; i++) {
      if (seats[i] != 0) {
        maxHeap.add(-seats[i]);
        minHeap.add(seats[i]);
      }
    }

    long max = 0;
    for (int i = 0; i < n; i++) {
      int t = -maxHeap.poll();
      max += t;
      if (t - 1 != 0)
        maxHeap.add(-(t - 1));
    }

    long min = 0;
    for (int i = 0; i < n; i++) {
      int t = minHeap.poll();
      min += t;
      if (t - 1 != 0)
        minHeap.add(t - 1);
    }

    System.out.println(max + " " + min);
  }
}

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.