whup1355.java

来自「<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关」· Java 代码 · 共 98 行

/*
 * Copyright (C) 2003-2008 Wang Pengcheng <[e-mail]>
 * Permission is granted to copy, distribute and/or modify this
 * document under the terms of the GNU Free Documentation License,
 * Version 2.0 or any later version published by the Free Software Foundation;
 * with no Invariant Sections.
 * You may obtain a copy of the License at
 *   http://www.gnu.org/licenses/lgpl.txt
 */
//16 Mar 2008
package cn.edu.whu.iss.algorithm.unit14.test;

import java.util.Scanner;
import java.util.TreeMap;

import cn.edu.whu.iss.algorithm.unit14.DynamicStatisticsTree;

public class WhuP1355 {

	static class Stand implements Comparable<Stand>{
		private int p;
		private String name;
		public int getP() {
			return p;
		}
		public void setP(int p) {
			this.p = p;
		}
		public String getName() {
			return name;
		}
		public void setName(String name) {
			this.name = name;
		}
		public Stand(int p, String name) {
			super();
			this.p = p;
			this.name = name;
		}
		public int compareTo(Stand o) {
			return this.p - o.getP();
		}
		
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		TreeMap<String, Integer> name = new TreeMap<String, Integer>();
		DynamicStatisticsTree<Stand> queue = new DynamicStatisticsTree<Stand>();
		Stand a = new Stand(0,"");
		queue.add(a);
		a = new Stand(5000000,"");
		queue.add(a);
		
		String n;
		Integer b,e;
		int p;
		int q;
		int t = in.nextInt();
		while (t-- > 0) {
			q = in.nextInt();
			while (q-- > 0) {
				int s = in.nextInt();

				if (s == 1) {
					n = in.next();
					p = in.nextInt();
					p += 2;
					if (p > queue.size()) {
						p = queue.size();
					}
					b = queue.selectStatisticData(p-1).getP();
					e = queue.selectStatisticData(p).getP();
					p = e-100;
					name.put(n, p);
					queue.add(new Stand(p,n));
				} else {
					n = in.next();
					p = name.get(n);
					a = new Stand(p,n);
					queue.remove(a);
				}
			}
			Object[] o =queue.toArray();
			for(int i=1;i<o.length-1;i++){
				Object c = o[i];
				System.out.println(((Stand)c).getName());
			}
		}

	}

}