Regionals 2004 Asia - Beijing Argus 小根堆

本文主要是介绍Regionals 2004 Asia - Beijing Argus 小根堆，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击打开链接

小根堆

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) {new Task().solve() ;  }	
}class Task{InputReader in = new InputReader(System.in) ;PrintWriter out = new PrintWriter(System.out) ;void solve(){size = 0 ;while(! "#".equals(in.next())){push(new Node(in.nextInt() , in.nextInt())) ;       	 }	int k = in.nextInt() ;while(k-- > 0){Node now = top() ;out.println(now.id) ;push(new Node(now.id , now.period , now.period + now.time)) ;}out.flush() ;}Node[] node = new Node[30008] ;int size ;void push(Node nd){node[++size] = nd ;int i = size ;while(i > 0){if((i>>1) <= 0) break ;if(node[i>>1].compareTo(node[i]) > 0){Node t = node[i] ;node[i] = node[i>>1] ;node[i>>1] = t ;i >>= 1 ;}else break ;}}Node top(){Node ret = node[1] ;node[1] = node[size--] ;int i = 1 ;while(i <= size){int nxid = i<<1 ;if(nxid > size) break ; if((i<<1|1) <= size){if(node[i<<1].compareTo(node[i<<1|1]) > 0)nxid = i<<1|1 ;}if(node[nxid].compareTo(node[i]) < 0){Node t = node[i] ;node[i] = node[nxid] ;node[nxid] = t ;i = nxid ;}else break ;} return ret ;}class Node implements Comparable<Node>{long period ;long time ;int id ;Node(int id , long period){this.id = id ;this.time = this.period = period  ;}Node(int id , long period, long time) {this.period = period;this.time = time;this.id = id;}	@Overridepublic int compareTo(Node o) {if(time == o.time) return Integer.compare(id , o.id) ;return Long.compare(time , o.time) ;}@Overridepublic String toString() {return "Node [period=" + period + ", time=" + time + ", id=" + id+ "]";}}}class InputReader {  public BufferedReader reader;  public StringTokenizer tokenizer;  public InputReader(InputStream stream) {  reader = new BufferedReader(new InputStreamReader(stream), 32768);  tokenizer = new StringTokenizer("");  }  private void eat(String s) {  tokenizer = new StringTokenizer(s);  }  public String nextLine() {  try {  return reader.readLine();  } catch (Exception e) {  return null;  }  }  public boolean hasNext() {  while (!tokenizer.hasMoreTokens()) {  String s = nextLine();  if (s == null)  return false;  eat(s);  }  return true;  }  public String next() {  hasNext();  return tokenizer.nextToken();  }  public int nextInt() {  return Integer.parseInt(next());  }  public long nextLong() {  return Long.parseLong(next());  }  public double nextDouble() {  return Double.parseDouble(next());  }  public BigInteger nextBigInteger() {  return new BigInteger(next());  }  }  

这篇关于Regionals 2004 Asia - Beijing Argus 小根堆的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---