日志统计

暴力（3/8）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
pair<int, int> a[N];
//cnt[i]id为i总共被点赞次数
//st[i]id为i是否满足题目条件
int n, d, k, cnt[N], st[N]; 
int main()
{
    cin>>n>>d>>k;
    for(int i=0; i<n; i++) scanf("%d %d", &a[i].first, &a[i].second);//ts id
    sort(a, a+n);
    for(int l=0; l+d<N; l++){//枚举每段长度为d的时间段
        memset(cnt, 0, sizeof cnt);
        for(int i=0; i<n; i++){//枚举所有在指定时间段范围的所有日志
            if(a[i].first >= l && a[i].first < l+d)
                cnt[a[i].second]++;
            if(cnt[a[i].second] >= k)//满足条件，记录
                st[a[i].second] = 1;
        }
    }
    for(int i = 0; i <= N; i++)
        if(st[i] == 1)
            printf("%d\n", i);
    return 0;
} 

双指针（8/8）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
pair<int, int> a[N];
int n, d, k, cnt[N], st[N]; 
int main()
{
    cin>>n>>d>>k;
    for(int i=0; i<n; i++) scanf("%d %d", &a[i].first, &a[i].second);//ts id
    sort(a, a+n);//按日期排序 
    for(int l=0, r=0; l<n; l++){//对日期区间进行双指针
        cnt[a[l].second]++;
        while(l>=r && a[l].first - a[r].first >= d){
            cnt[a[r].second]--;
            r++;
        }
        if(cnt[a[l].second] >= k)//满足条件，记录
            st[a[l].second] = 1;
    }
    for(int i = 0; i <= N; i++)
        if(st[i] == 1)
            printf("%d\n", i);
    return 0;
}