HDU1896（队列应用）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1896
package D0725;import java.util.*;import java.io.*;public class HDu1896 {public static void main(String[] args) throws IOException {StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));PriorityQueue<Stone> pq = new PriorityQueue<Stone>();// 用LInkedList超时int t;st.nextToken();t = (int) st.nval;int n;while (t-- > 0) {pq.clear();st.nextToken();n = (int) st.nval;int pi, di;while (n-- > 0) {st.nextToken();pi = (int) st.nval;st.nextToken();di = (int) st.nval;Stone stone = new Stone(pi, di);pq.add(stone);}// 将扔出去的石头加入队列。忽略下一个石头（偶数石头），当处理到队列中最后一个的时候就是结果int result = 0;// 结果while (!pq.isEmpty()) {Stone s = pq.poll();int spi = s.pi + s.di;Stone sto = new Stone(spi, s.di);pq.add(sto);pq.poll();// 将下一个石头（偶数）留在原地if (pq.isEmpty())result = s.di + s.pi;}System.out.println(result);}}}class Stone implements Comparable<Stone> {public int pi, di;public Stone(int pi, int di) {this.pi = pi;this.di = di;}@Overridepublic int compareTo(Stone o) {if (pi < o.pi)return -1;else if (pi == o.pi) {if (di < o.di)return -1;}return 1;}}