解题思路:map中键存储id 值存储时间,将所有的信息录入后对时间进行从小到大排序.遍历map,创建两个指针i=0,j=k-1,代表维护的滑动窗口的大小为k,当j指向的元素减去i指向的元素的结果小于等于D时,说明该id满足要求,否则i++,j++即窗口向右滑动1位.
注意事项:由于unordered_map并不会按顺序存储id,因此找到符合要求的id时存入set容器.然后遍历输出set容器元素.
参考代码:
#include <bits/stdc++.h> typedef long long ll; #define f first #define s second using namespace std; int main(){ unordered_map<ll,vector<int>> map; ll n,d,k,t,id; set<ll> res; cin>>n>>d>>k; for(int i=0;i<n;i++){ scanf("%lld %lld",&t,&id); map[id].emplace_back(t); } ll len=map.size(),i,j; for(auto x:map){ i=0,j=k-1; sort(x.s.begin(),x.s.end()); while(j<x.s.size()){ if((x.s[j]-x.s[i]+1)<=d){ res.insert(x.f); break; } i++,j++; } } for(auto f:res)printf("%lld \n",f); return 0; }
0.0分
2 人评分
C语言程序设计教程(第三版)课后习题6.2 (C语言代码)浏览:1420 |
C语言程序设计教程(第三版)课后习题11.1 (C语言代码)浏览:489 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:1479 |
交换Easy (C语言代码)浏览:761 |
链表数据求和操作 (C语言代码)浏览:952 |
分解质因数 (C++代码)浏览:1482 |
C语言训练-最大数问题 (C语言代码)浏览:591 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:612 |
1063题 初学者,求帮忙看下,不知道哪错了浏览:232 |
母牛的故事 (C语言代码)浏览:503 |