解题思路:双指针i表示右端点,j表示左端点,如果i~j区间<k那么每次都把i扩展的点的权值加进来,当i-j的距离大于等于k时,那么左端点往右挪,并删除点原先端点的贡献,然后判断当前扩展的点的热度是否符合要求,符合就打标记,最后遍历所有可能是帖子id,有标记的就是答案

  1. #include<bits/stdc++.h>
  2. #define x first
  3. #define y second
  4. #define mem1(h) memset(h,-1,sizeof h)
  5. #define mem0(h) memset(h,0,sizeof h)
  6. #define mcp(a,b) memcpy(a,b,sizeof b)
  7. using namespace std;
  8. typedef long long LL;
  9. typedef unsigned long long ull;
  10. typedef pair<int,int>PII;
  11. typedef pair<double,double>PDD;
  12. namespace IO{
  13. inline LL read(){
  14. LL o=0,f=1;char c=getchar();
  15. while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
  16. while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
  17. return o*f;
  18. }
  19. }using namespace IO;
  20. //#############以上是自定义技巧(可忽略)##########
  21. const int N=1e5+7,M=2e5+7,INF=0x3f3f3f3f,mod=1e8+7,P=131;
  22. int n,d,k;
  23. PII a[N];
  24. int cnt[N];
  25. bool st[N];
  26. int main(){
  27. n=read(),d=read(),k=read();
  28. for(int i=0;i<n;i++){
  29. a[i].x=read(),a[i].y=read();
  30. }
  31. sort(a,a+n);
  32. for(int i=0,j=0;i<n;i++){//i表示右端点,j表示左端点
  33. cnt[a[i].y]++;//加上当前i扩展的点的热度
  34. while(a[i].x-a[j].x>=d){//如果右端点的距离与左端点的距离大于等于k就把左端点右移
  35. cnt[a[j].y]--;//把删除左端点的贡献
  36. j++;
  37. }
  38. if(cnt[a[i].y]>=k)st[a[i].y]=true;//当前扩展点的id的热度符合要求就标记
  39. }
  40. for(int i=0;i<N;i++){
  41. if(st[i])printf("%d\n", i);
  42. }
  43. return 0;
  44. }
点赞(0)
 

7.3 分

2 人评分

 

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 1 条评论

xr 2年前 回复TA
为什么要把左端点的贡献--