BoxesDiv2——SRM 622 DIV2

1490 ワード

import java.util.*;
public class BoxesDiv2{
    public     BoxesDiv2(){}


    public int findSize(int[] candyCounts)
    {
        Arrays.sort(candyCounts);
        for(int i=0;i<candyCounts.length;i++){
            int v = candyCounts[i];
            int j=1;
            while(j<v){
                j<<=1;
            }
            candyCounts[i]=j;
        }
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(candyCounts.length);
        for(int i=0;i<candyCounts.length;i++){
            pq.add(candyCounts[i]);
        }
        while(!pq.isEmpty()){
            Integer v1 = pq.peek();
            pq.poll();
            if(pq.isEmpty()){
                return v1;
            }
            Integer v2=		pq.peek();
            pq.poll();
            int v3 = v1+v2;
            int j=1;
            while(j<v3){
                j<<=1;
            }
            pq.add(j);
        }
        return 1;
    }
}

考え方:
上2の指数べき乗を整数化し、
すなわち、1-』1;2--》2;3,4--》4;5,6,7,8--》8
(1)すべての要素を上へ2の指数べき乗で整数化する.
(2)スタックを使用して、すべての要素をスタックに入れる
(3)スタックに1つの要素しかない場合は、スタックを出て、スタックトップ要素を返します.
(4)そうでない場合は,スタックトップ2の要素を取り,加算した後,上2の指数べき乗を整数化してスタックに入れる.
このステップは、実際にはこの2つの数の大きな要素に2を乗じるだけでよい.