你好呀，我是灰小猿，一個超會寫bug的程式猿！

歡迎大家關注我的專欄“每日藍橋”，該專欄的主要作用是和大家分享近幾年藍橋杯省賽及決賽等真題，決議其中存在的演算法思想、資料結構等內容，幫助大家學習到更多的知識和技術！

標題：日志統計

小明維護著一個程式員論壇，現在他收集了一份”點贊”日志，日志共有 N行，其中每一行的格式是：

ts id

表示在 ts時刻編號id的帖子收到一個”贊”，現在小明想統計有哪些帖子曾經是”熱帖”，如果一個帖子曾在任意一個長度為 D的時間段內收到不少于 K

個贊，小明就認為這個帖子曾是”熱帖”，

具體來說，如果存在某個時刻 T滿足該帖在 [T,T+D) 這段時間內(注意是左閉右開區間)收到不少于 K個贊，該帖就曾是”熱帖”，

給定日志，請你幫助小明統計出所有曾是”熱帖”的帖子編號，

輸入格式

第一行包含三個整數 N,D,K，

以下 N行每行一條日志，包含兩個整數 ts 和 id，

輸出格式

按從小到大的順序輸出熱帖 id，

每個 id占一行，

資料范圍

1≤K≤N≤105,
0≤ts,id≤105,
1≤D≤10000

輸入樣例：

7 10 2

0 1

0 10

10 10

10 1

9 1

100 3

100 3

輸出樣例：

1

3

資源約定: .

峰值記憶體消耗(含虛擬機) < 256M

CPU消耗< 1000ms

請嚴格按要求輸出，不要畫蛇添足地列印類似:“ 請您輸...”的多余內容.

所有代碼放在同-一個源檔案中，除錯通過后，拷貝提交該原始碼.

不要使用package陳述句，不要使用jdk1.7及以上版本的特性，

主類的名字必須是: Main, 否則按無效代碼處理.

解題思路

本題在求解的時候，我們可以考慮先將用戶輸入的每個帖子的點贊時間記錄下來，然后對該點贊時間進行排序，找出在區間D內點贊數量最多的那個區間，只要在D區間內的點贊數量大于K，則將其存盤到SortedSet中，SortedSet是一個可以對元素進行自動排序，且輸入資料不重復的資料型別，對每一個帖子及其點贊時間的存盤可以使用map，key為整型資料，表示帖子的編號，后面的value為list串列，其中存盤該編號帖子的點贊時間，最后按照上述方法進行判斷即可，

答案原始碼：

package 一八年省賽真題;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

public class Year2018_Bt8 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();	//帖子數量
		int D = scanner.nextInt();	//時間
		int K = scanner.nextInt();	//熱帖指標
		Map<Integer, List<Integer>> tiezhi = new HashMap<Integer, List<Integer>>();
		HashSet<Integer> idSet = new HashSet<Integer>();
//		int [][] dataArr = new int[N][2];
		SortedSet<Integer> ansSet = new TreeSet<Integer>();
		for (int i = 0; i < N; i++) {
			int ts = scanner.nextInt();	//點贊時間
			int id = scanner.nextInt();	//點贊的帖子號
			
			idSet.add(id);
			//如果資料是第一次記錄
			if (tiezhi.get(id)==null) {
				List<Integer> list = new ArrayList<Integer>();
//				System.out.println(id + " " + ts);
				list.add(ts);
				tiezhi.put(id, list);
			} else {
				List<Integer> list = new ArrayList<Integer>();
				list = tiezhi.get(id);
//				System.out.println(id + " " + ts);
				list.add(ts);
				tiezhi.put(id, list);
			}											
		}
		//遍歷每一個存盤的帖子的id
		for (Integer ids : idSet) {
			//將每一個帖子對應的點贊時間放置到陣列中，并對該陣列排序
			List<Integer> list = tiezhi.get(ids);
			int [] tsArr = new int[list.size()];
			for (int i = 0; i < list.size(); i++) {
//				System.out.print(ids + ": " + list.get(i) + " ");
				tsArr[i] = list.get(i);
			}
			Arrays.sort(tsArr);
			
			//遍歷存放時間的陣列，看其中在D時間區間內有沒有點贊數大于K的情況
			for (int i = 0; i < tsArr.length; i++) {
				int j = i;
				int count = 0;
				while(j<tsArr.length && (tsArr[j]-tsArr[i])<D) {
//					System.out.println(ids + " " + tsArr[j] + "-" + tsArr[i]);
					count++;
					j++;
				}
				//如果存在點贊數大于K的帖子，則記錄id
				if (count>=K) {
					ansSet.add(ids);
				}
			}
		}
		
		for (Integer integer : ansSet) {
			System.out.println(integer);
		}		
					
	}

}