CSDN

蓝桥杯-日志统计

2024-05-22 16:34 由 小程xy 发表于 #其他

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。

其中每一行的格式是：

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

现在小明想统计有哪些帖子曾经是”热帖”。

如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是”热帖”。

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

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

输入格式

第一行包含三个整数 N,D,K。

以下 N 行每行一条日志，包含两个整数 ts 和 id。

输出格式

按从小到大的顺序输出热帖 id。

每个 id 占一行。

数据范围

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

输入样例：

7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

输出样例：

1
3

题解:

这题正常暴力会超时

暴力代码👇(只能过不到一半数据)

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 1e5 + 10;
int cnt[N];  // 统计帖子在某个时间中出现的次数
bool st[N];  // 帖子是否是热帖
vector<pair<int,int>> v;
int main()
{
	int n, d, k; cin >> n >> d >> k;
	v.resize(n);
	
	for (int i = 0; i < n; i ++)
		cin >> v[i].x >> v[i].y;
	
	sort(v.begin(), v.end());
	
	for (int i = 0; i < n; i ++)
	{
		memset(cnt, 0, sizeof cnt);
		for (int j = i; v[j].x < v[i].x + d; j ++)
		{
			cnt[v[j].y] ++;
			if (cnt[v[j].y] >= k) 
				st[v[j].y] = true;
		}	
	}
	
	for (int i = 0; i < N; i ++)
		if (st[i]) cout << i << endl;
	return 0;
}

最优解:

  1. 先对输入的 st 和 id 进行排序
  2. 维护一个滑动窗口, 窗口的时间长度是 d, 每次当窗口往下移动的时候, 减去前面出现时间过早的帖子id, 加上后面进来的一个帖子id。 ( 每次只进来一个帖子, 但可能出去很多个帖子, 因为需要让整个窗口中的帖子的时间差在 区间[刚进来的帖子的st, 刚进来的帖子的st - (d - 1)] )
  3. 判断帖子是否是热帖

题中要求的时间区间是[t, t + d), 我们代码中维护的区间是[t, t + d - 1]
ac代码👇

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 1e5 + 10;
int cnt[N];  // 帖子出现的次数
bool st[N];  // 是否是热帖
vector<pair<int,int>> v;
int main()
{
	int n, d, k; cin >> n >> d >> k;
	v.resize(n);
	
	for (int i = 0; i < n; i ++) cin >> v[i].x >> v[i].y;
	
	sort(v.begin(), v.end());
	
	for (int i = 0, j = 0; i < n; i ++)
	{
	    int id = v[i].y;
		cnt[id] ++;
		
        // 不理解为什么用的while 而不是 if的话, 看代码下面的图片
		while (v[i].x - v[j].x >= d) // 使时间区间满足 [t, t + d - 1]
		{
			cnt[v[j].y] --;
			j ++;
		}
		
		if (cnt[id] >= k) st[id] = true;
	}

	for (int i = 0; i < N; i ++)
		if (st[i]) cout << i << endl;
	return 0;
}

当 d = 10, t = 25的时候, 此时下标 j 应该在18的下标的前面, 因为 25 - 18 = 7 (小于d), 当 i ++ 后, t = 30, 此时 j 应该是21对应的下标
下标i加一, j 加的可能不只是1

觉得写的不错的话, 点个赞吧~

热门相关：腹黑boss霸宠：逃妻，吻我   重生之悠然人生   小姨子的秘密   年轻的嫂子5   梦精记