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);
}
}

### Like this:

Like Loading...