【摘要】 你好呀，我是灰小猿，一个超会写bug的程序猿！
欢迎大家关注我的专栏“每日蓝桥”，该专栏的主要作用是和大家分享近几年蓝桥杯省赛及决赛等真题，解析其中存在的算法思想、数据结构等内容，帮助大家学习到更多的知识和技术！

标题：日志统计
小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N行。其中每一行的格式是：
ts id
表示在 ts时刻编号…

你好呀，我是灰小猿，一个超会写bug的程序猿！

欢迎大家关注我的专栏“每日蓝桥”，该专栏的主要作用是和大家分享近几年蓝桥杯省赛及决赛等真题，解析其中存在的算法思想、数据结构等内容，帮助大家学习到更多的知识和技术！

标题：日志统计

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N行。其中每一行的格式是：

tsid

表示在 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);

       		}

       	}

       }

   


                    
        
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
软件开发