凡森Zfans

用户名：Zfans

访问量：34258

签　名：

路漫漫其修远兮，吾将上下而求索。

等　　级
排　　名	157
经　　验	7174
参赛次数	0
文章发表	105
年　　龄	21
在职情况	学生
学　　校	重庆交通大学
专　　业	计算机科学与技术

　　自我简介：

热爱学习的大学生。

TA的其他文章

蓝桥杯2013年第四届真题-带分数（C++代码） by Zfans.
浏览：340

蓝桥杯算法提高VIP-十进制数转八进制数 -题解(C++代码) by Zfans.
浏览：297

蓝桥杯2013年第四届真题-幸运数-题解(C++代码) by Zfans.
浏览：799

你可能喜欢

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

蓝桥杯2018年第九届真题-日志统计-题解（C++代码）

　　作者: 凡森Zfans　　　　发表时间：2020-08-24 15:18:22 浏览：720　|　评论：1　

原题链接：蓝桥杯2018年第九届真题-日志统计

```cpp
/*日志统计

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

ts id

表示在ts时刻编号id的帖子收到一个"赞"。

现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞，小明就认为这个帖子曾是"热帖"。

具体来说，如果存在某个时刻T满足该帖在[T, T+d)这段时间内(注意是左闭右开区间)收到不少于K个赞，该帖就曾是"热帖"。

给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。

【输入格式】
第一行包含三个整数N、D和K。
以下N行每行一条日志，包含两个整数ts和id。

对于50%的数据，1 <= k <= n <= 1000
对于100%的数据，1 <= k <= n <= 100000 0 <= ts <= 100000 0 <= id <= 100000

【输出格式】
按从小到大的顺序输出热帖id。每个id一行。

【输入样例】
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

【输出样例】
1
3

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗  < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。
*/

#include<bits/stdc++.h>

using namespace std;

struct R {
    int ts, id;
};

bool cmp(R a, R b) {
    return a.ts < b.ts;
}

int n, d, k;

int main() {

ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

cin >> n >> d >> k;

vector <R> records(n);

map<int, int> cnt;

for (int i = 0; i < n; ++i) {
        cin >> records[i].ts >> records[i].id;
    }

sort(records.begin(), records.end(), cmp);

int j = 0;

set<int> answers;

for (int i = 0; i < n; ++i) {
        while (j < n && records[j].ts - records[i].ts < d) {
            cnt[records[j].id]++;
            if (cnt[records[j].id] >= k) {
                answers.insert(records[j].id);
            }
            j++;
        }
        cnt[records[i].id]--;
    }

for (set<int>::iterator i = answers.begin(); i != answers.end(); ++i) {
        cout << *i << '\n';
    }

return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

uq_59528053940

时间复杂度是O(n2),后面数大了就超时了，不能拿满分的这个题解

2022-03-14 15:11:54

凡森Zfans

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.2 （C++代码）

C语言训练-谁家孩子跑最慢* （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

蓝桥杯历届试题-九宫重排（C++代码）

蓝桥杯2018年第九届真题-日志统计-题解（C++代码）

评论区

精彩推荐

【密码】（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

简单的a+b （C语言代码）

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

WU-复数求和（C++代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

矩阵乘方（C语言代码）

凡森Zfans

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.2 （C++代码）

C语言训练-谁家孩子跑最慢* （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

蓝桥杯历届试题-九宫重排 （C++代码）

蓝桥杯2018年第九届真题-日志统计-题解（C++代码）

评论区

精彩推荐

【密码】 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

简单的a+b （C语言代码）

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

WU-复数求和 （C++代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

矩阵乘方 （C语言代码）

蓝桥杯历届试题-九宫重排（C++代码）

　　评论区

【密码】（C语言代码）

WU-复数求和（C++代码）

矩阵乘方（C语言代码）