I assumed this should be a rather simple problem, and I tested my code on my pc for all kinds of input.
But I can' t get ACed anyway. I wonder if there's anything I'm doing wrong.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
public class Main {
/**
* 3375. Stamps
*
* @param args
*/
public static void main(String[] args) {
// int total = 11;
// String input ="1 9 8";
// System.out.println(calcMin(total, input));
doFunc();
}
private static void doFunc() {
try {
BufferedReader reader = new BufferedReader(new InputStreamReader(
System.in));
String str = reader.readLine();
int count = Integer.valueOf(str);
List<String> stringList = new ArrayList<String>();
List<Integer> totalList = new ArrayList<Integer>();
for (int i = 0; i < count; ++i) {
str = reader.readLine();
totalList.add(Integer.valueOf(str.split(" ")[0]));
str = reader.readLine();
stringList.add(str);
}
reader.close();
for (int i = 0; i < count; ++i) {
System.out.println("Scenario #" + (i + 1) + ":");
int r = calcMin(totalList.get(i), stringList.get(i));
if (r != -1) {
System.out.println(r);
} else {
System.out.println("impossible");
}
System.out.println();
}
} catch (NumberFormatException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
private static int calcMin(int total, String input) {
String[] tokens = input.split(" ");
int[] intArray = new int[tokens.length];
for (int i = 0; i < intArray.length; ++i) {
intArray[i] = Integer.valueOf(tokens[i]);
}
PriorityQueue<Integer> heap = new PriorityQueue<Integer>(
intArray.length, new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
for (int i : intArray) {
heap.add(i);
}
int count = 0;
while (!heap.isEmpty()) {
int number = heap.poll();
total -= number;
++count;
if (total <= 0) {
break;
}
}
if (total > 0) {
return -1;
}
return count;
}
}
