蓝桥 日志统计 边界判断 python

想说的话

大家好，我是 @愿此后再无WA，可以叫我小A，也可以叫我愿愿，一位阳光帅小伙，对算法领域比较感兴趣。如果我的文章对您有用，欢迎持续关注，我们一起进步！

很抱歉各位，现离蓝桥杯比赛不到一个月时间，我临时改变了计划，转为全心备战蓝桥，因为这个省一对我来说太重要了，也是我最后一次机会，我一定要拿到手，那么这样的话我在博客上花的时间就会少了很多，也将导致博客文章质量明显下降，在此我给大家说声抱歉

这些日子我真的很开心，博客上能遇到一群志同道合的兄弟姐妹真的很幸福，没有你们的支持与鼓励我早就坚持不下去了，因为有你们我才能走的更远☀️☀️熬过这段时期我一定会回来的，爱你们❤️❤️

日志统计

吐槽

我想问是题目变简单了还是稍微找到题感了？今天执梗老大哥出的题有点舒服，起码能够想到怎么做，如果比赛出这种题就爽歪歪。当然，如果真是比赛的话我可能还是0分，因为！我又没有看清楚题！我发现做十道题，八道题理解错题意了，我的妈再这样下去可不行啊！幸好，第一个样例错了，找到了问题根源，不然又要死不瞑目了哈哈哈。

思路

说实话我没做过这种类型的题，但是给我的感觉就肯定不能一个一个找然后累加判断。想了一下发现只需要判断边界点就ok。

我们以id为键，ts为值，将其存入到字典中。然后将每个id的ts按从小到大排序。接着就是判断第i个ts与第i+k-1个ts的差值是否小于d.这里的k表示点赞数，d表示时间戳。其实我们就是判断要第一个可能符合条件的区间。对于每个i位置的ts而言，由他作为起始值的区间能否上热帖就要看第i+k-1个ts（这个位置是所需最少点赞量），这是以i位置ts作为起始值的最前判断结束区间，如果这个区间符合条件那一定符合，如果这个区间不符合条件，这个区间往后扩大同样不符合。如果不太明白可以结合代码手写模拟一下过程。

再然后就是一些剪枝判断了，如ts的数量都少于所需点赞量那必然不能够上热榜。

最后就是排序问题，它给出的数据不是有序的，存入到字典的id值也不是按顺序，一开始我没发现就提交了，结果0分，不过也幸好0分，就能看测试用例了，发现需要排序。

发现内存占用不高，所以任性一下， 使用一个列表将结果全部保存，然后排序再输出。

对比一下好像也不是很高。

代码

N,D,K = map(int,input().split())dic = {}
output = []  # 输出的id不是有序的，将其放入到output排序后再输出，内存大，任性for _ in range(N):t,i = map(int,input().split())if i not in dic:dic[i] = [t]else:dic[i].append(t)for i in dic:l = dic[i]length = len(l)if length < K:continuel.sort()for j in range(length):if j+K-1 < length:if l[j+K-1] - l[j] < D:output.append(i)  breakoutput.sort()
for i in output:print(i)