MinPQ.java

mport java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class MinPQ {
    
    int N;
    int capacity;
    int [] array;
    
    MinPQ(int N){
        this.capacity = N+1;
        N=0;
        array = new int[capacity];
    }
    
    void insert(int x){
        if(N==array.length-1){
            resize(array.length*2);
        }
        int hole = ++N;
        for(;hole>1 && x < array[hole/2];hole/=2)
            array[hole]=array[hole/2];
        
        array[hole]=x;
    }
    
    int min(){
        return array[1];
    }
    
    void deleteMin(){
        array[1]=array[N--];
        percolateDown(1);
    }
    
    private void resize(int capacity) {
        
        int[] temp = new int[capacity];
        for (int i = 1; i <= N; i++) {
            temp[i] = array[i];
        }
        array = temp;
    }
    void percolateDown(int hole){
        
        int child;
        int temp = array[hole];
        
        for(;hole*2<=N;hole=child){
            child = hole*2;
            if(child != N && array[child+1]<array[child]){
                child++;
            }
            if(array[child]<temp){
                array[hole] = array[child];
            }else {
                break;
            }
        }
        array[hole]= temp;
    }
    int size(){
    	return N;
    }


    public static void main(String[] args) {
        
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int K = scan.nextInt();
        MinPQ minPQ = new MinPQ(N);    
        
        for(int i=1;i<=N;i++)
            minPQ.insert(scan.nextInt());
        
        int trials =0;
        while(minPQ.min()<K)
        {
            
            trials++;
            
            if(minPQ.size()>1){
            	int firstCookie = minPQ.min();
            	minPQ.deleteMin();
            	int secondCookie = minPQ.min();
            	minPQ.deleteMin();
            	int newCookie = firstCookie+2*secondCookie;
            	if(newCookie >=K){
            		break;
            	}else{
            		minPQ.insert(newCookie);
            	}
            }else{
            	trials =-1;
            	break;
            }
        }
        System.out.println(trials);
    }
    
}