日志统计(暴力/哈希+二分/双指针滑动窗口三种方法 后两种ac)
三种方法:
1.暴力(TLE)
2.二分+哈希(自己写的)
3.双指针滑动窗口
二分+哈希和滑窗均可ac
方法1:暴力 过了13/15个测试数据
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
const int N = 1e5 + 10;
int n, d, k;
struct myid{
vector<int>time; //存的是每个id被点赞的时间
}ids[N];
int main(){
cin >> n >> d >> k;
set<int> hash;
for(int i = 0; i < n; i ++){
int ts, id;
cin >> ts >> id;
if(!hash.count(id)) hash.emplace(id);
ids[id].time.push_back(ts);
}
for(auto i : hash){ //遍历每个id
sort(ids[i].time.begin(), ids[i].time.end()); //给每个id点赞的时间排序
for(int j = 0; j < ids[i].time.size(); j ++){
int sum = 0;
for(int k = j; k < ids[i].time.size(); k ++){
if(ids[i].time[j] + d <= ids[i].time[k]) break;
sum ++;
}
if(sum >= k){
cout << i << endl;
break;
}
}
}
return 0;
}
方法2 : 在搜索的时候优化一层二分 成功ac
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
const int N = 1e5 + 10;
int n, d, k;
struct myid{
vector<int>time; //存的是每个id被点赞的时间
}ids[N];
int main(){
cin >> n >> d >> k;
set<int> hash;
for(int i = 0; i < n; i ++){
int ts, id;
cin >> ts >> id;
if(!hash.count(id)) hash.emplace(id);
ids[id].time.push_back(ts);
}
for(auto i : hash){ //遍历每个id
sort(ids[i].time.begin(), ids[i].time.end()); //给每个id点赞的时间排序
for(int j = 0; j < ids[i].time.size(); j ++){
int sum = 0;
int l = j, r = ids[i].time.size() - 1; //二分查找第一个不满足条件的点的idx
while(l < r){
int mid = l + r >> 1;
if(ids[i].time[j] + d <= ids[i].time[mid]) r = mid;
else l = mid + 1;
}
//特判一下二分到的点是否真不满足
if(ids[i].time[j] + d <= ids[i].time[r]) sum = r - j;
else sum = r - j + 1;
if(sum >= k){
cout << i << endl;
break;
}
}
}
return 0;
}
方法3 :存储方式按时间线存,然后枚举时间d,通过双指针滑动窗口优化重复枚举的中间步骤
#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, d, k;
PII times[N]; // 时间轴存入
int cnt[N]; // 存D时间内的id的发帖数目
bool st[N]; // 存id=idx的帖子是否为热帖
int main(){
cin >> n >> d >> k;
for(int i = 0; i < n; i ++){
int ts, id;
cin >> ts >> id;
times[i]. x = ts;
times[i].y = id;
}
sort(times, times + n);
for(int i = 0, j = 0; i < n; i ++){
int id = times[i].y;
cnt[id] ++;
while(times[j].x + d <= times[i].x){
cnt[times[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;
}
666
低调