BoxesDiv2——SRM 622 DIV2
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を乗じるだけでよい.