返回题解分享
讨论 / 题解分享/ 帖子详情

日志统计(编程题) - 题解

#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define LL long long
#define endl '\n'

const int N = 1e5 + 10;
typedef pair<int, int> PII;

int n, D, K; // n表示日志个数,D表示连续时间,K表示点赞不小于此值就为热帖
PII logs[N]; // 存放日志:某一ts时刻和帖子id
int like[N]; // 存放每个帖子id的点赞数
bool st[N]; // 存放每个帖子id是否为热帖,true是热帖,false不是热帖

void solve()
{
	cin >> n >> D >> K;

	for (int i = 0; i < n; i++) cin >> logs[i].first >> logs[i].second;

	sort(logs, logs + n);

	for (int i = 0, j = 0; i < n; i++)
	{
		int _id = logs[i].second; // 提取每条日志中的帖子id
		like[_id]++; // 对应id的帖子点赞数+1

		/* 如果某个时刻T不满足该贴在[T, T+D) 这段时间内,去除过期点赞
			ts: 0  0  9  10  10  100  100
			    i
				j
			↓
			ts: 0  0  9  10  10  100  100
			       i
				j
			↓
			ts: 0  0  9  10  10  100  100
			          i
				j
			↓
			ts: 0  0  9  10  10  100  100 (进入while,去除过期点赞)
			             i
				j
			...
			ts: 0  0  9  10  10  100  100 (退出while)
			             i
				      j
		*/
		while (logs[i].first - logs[j].first >= D)
		{
			like[logs[j].second]--;
			j++;
		}

		if (like[_id] >= K) st[_id] = true; // 符合条件的帖子id将被标记为热帖
	}

	for (int i = 0; i < 1e5; i++)
		if (st[i]) cout << i << endl; // 输出热帖编号
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	solve();

	return 0;
}
0 回复 0 转发 0 喜欢 0 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!