在国外建网站方便吗,淄博外贸网站哪家好,wordpress好玩的主题,成都装修公司一览表题目#xff1a;
1238. 日志统计 题目 提交记录 讨论 题解 视频讲解 小明维护着一个程序员论坛。现在他收集了一份”点赞”日志#xff0c;日志共有 NN 行。
其中每一行的格式是#xff1a;
ts id 表示在 tsts 时刻编号 idid 的帖子收到一个”赞”。
现在小明想…题目
1238. 日志统计 题目 提交记录 讨论 题解 视频讲解 小明维护着一个程序员论坛。现在他收集了一份”点赞”日志日志共有 NN 行。
其中每一行的格式是
ts id 表示在 tsts 时刻编号 idid 的帖子收到一个”赞”。
现在小明想统计有哪些帖子曾经是”热帖”。
如果一个帖子曾在任意一个长度为 DD 的时间段内收到不少于 KK 个赞小明就认为这个帖子曾是”热帖”。
具体来说如果存在某个时刻 TT 满足该帖在 [T,TD)[T,TD) 这段时间内(注意是左闭右开区间)收到不少于 KK 个赞该帖就曾是”热帖”。
给定日志请你帮助小明统计出所有曾是”热帖”的帖子编号。
输入格式
第一行包含三个整数 N,D,KN,D,K。
以下 NN 行每行一条日志包含两个整数 tsts 和 idid。
输出格式
按从小到大的顺序输出热帖 idid。
每个 idid 占一行。
数据范围
1≤K≤N≤1051≤K≤N≤105, 0≤ts,id≤1050≤ts,id≤105, 1≤D≤100001≤D≤10000
输入样例
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3输出样例
1
3难度中等时/空限制1s / 64MB总通过数20816总尝试数43559来源 第九届蓝桥杯省赛C B组第九届蓝桥杯省赛Java B组 算法标签 挑战模式
代码
#include bits/stdc.h
using namespace std;typedef pairint,int PII;
const int N1e510;PII logs[N];
int cnt[N];//记录每个id的点赞数
bool st[N];//用来标记id号因为id 1e5所以可以利用遍历来输出。int main(){int n,d,k;cinndk;for(int i0;in;i){cinlogs[i].firstlogs[i].second;}//对时刻进行排序sort(logs,logsn);//i在前面,j在后面。区间[j,i]表示时间间隔为d。双指针是对应的时刻。int i,j;for(i0,j0;in;i){int tlogs[i].second;//记录下此刻帖子的idcnt[t];//点赞数量while(logs[i].first-logs[j].firstd){//当时间间隔大于d时说明超出窗口的长度移动j。等于d但是区间要求是左闭右开i此刻取到了但不应该取到所以减小区间,jcnt[logs[j].second]--;//去掉j时刻所指的id赞数j;}if(cnt[t]k) st[t] true;//为什么不直接输出有可能会重复在一个区间内满足了另一个区间内该id又满足了。所以直接加st数组判断就行//也可用用setint result数组存储idset集合有序唯一。。 result.insert(t);for (int t : result) 输出t}for (int i 0; i 100000; i ) if (st[i]) cout i endl;return 0;
}
思路
该题的标签提示我是双指针和滑动窗口
时间范围内点赞可用考虑先排序对时间。由于ts与id是一一对应的而且还要排序所以可用pair来表示 pairint,int logs;logs[i].first,logs[i].second;
双指针j,i左右指针指向一个时刻区间
滑动窗口[T,TD)时间时间间隔小于d
