学步园

   悲剧的poj2051 最小堆，奉献了无数次后才AC。这道题就是个最小堆，把最先到达的query输出query编号，然后继续排队等待同样的时间，要是某几个请求同时到达的话，就要按照编号从小到大的输出。通过这道题感觉自己考虑问题不够全面。

  废话少说了，看下面的代码吧：

  package poj;</p> <p>import java.util.Scanner;</p> <p>public class Main2051 {<br /> private static Query[] query = new Query[1002];</p> <p> public static void main(String[] args) {<br /> Scanner sc = new Scanner(System.in);</p> <p> int i = 0;<br /> while (sc.hasNext()) {<br /> String s = sc.nextLine();<br /> if (s.equals("#")) {<br /> int k = sc.nextInt();<br /> slove(k, i);<br /> break;<br /> }<br /> String[] str = s.split(" ");<br /> Query q = new Query();<br /> q.d = Integer.parseInt(str[1].trim());<br /> q.w = Integer.parseInt(str[2].trim());<br /> q.p = q.w;<br /> insertHeap(q, i);<br /> i++;<br /> }<br /> }</p> <p> public static void slove(int k, int n) {<br /> // System.out.println("start.........");</p> <p> while (k > 0) {<br /> System.out.println(query[0].d);<br /> query[0].w += query[0].p;<br /> // System.out.println(query[0].w);<br /> keapHeap(n);<br /> --k;<br /> }</p> <p> }</p> <p> public static void keapHeap(int n) {</p> <p> Query q = query[0];<br /> // System.out.println(q.w + ";" + q.d);<br /> int i = 0;<br /> int j = (i << 1) + 1;<br /> while (j <= n - 1) {<br /> if (j < n - 1 && query[j].w > query[j + 1].w)<br /> j++;<br /> else if (j < n - 1 && query[j].w == query[j + 1].w<br /> && query[j].d > query[j + 1].d) {<br /> j++;<br /> }<br /> if (query[j].w < q.w) {<br /> query[i] = query[j];<br /> i = j;<br /> } else if (query[j].w > q.w)<br /> break;<br /> else if (query[j].w == q.w && query[j].d < q.d) {<br /> query[i] = query[j];<br /> i = j;<br /> } else<br /> break;<br /> j = (i << 1) + 1;<br /> }<br /> query[i] = q;<br /> }</p> <p> public static void insertHeap(Query q, int n) {<br /> // System.out.println("n = " + n);<br /> if (n == 0) {<br /> query[0] = q;<br /> } else {</p> <p> int i = n;<br /> int j = (i - 1) >> 1;</p> <p> while (j >= 0) {<br /> if (query[j].w > q.w) {<br /> query[i] = query[j];<br /> i = j;<br /> } else if (query[j].w == q.w && query[j].d > q.d) {<br /> query[i] = query[j];<br /> i = j;<br /> } else<br /> break;<br /> j = (i - 1) >> 1;<br /> }<br /> query[i] = q;<br /> }<br /> }</p> <p> static class Query {<br /> private int w;<br /> private int p;<br /> private int d;<br /> }<br /> }</p> <p>