求助0分

LiaoYF @ 2022-12-22 11:05:04

#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;
int n,d,k,zan[100005];
struct lik{
    int ts,id;
}a[100005];
bool cmp(lik x,lik y){
    return x.ts<y.ts;
}
deque<int> q;
int main(){
    cin>>n>>d>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i].ts>>a[i].id;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        while(!q.empty()&&a[i].ts-a[q.front()].ts>=d)q.pop_front();
        q.push_back(i);
        for(int j=0;j<q.size();j++){
            zan[a[q[j]].id]++;
        }
    }
    for(int i=1;i<=n;i++){
        if(zan[i]>=k){
            cout<<i<<"\n";
        }
    }
    return 0;
}

by char_cha_ch @ 2022-12-22 11:09:00

建议对于每一种贴进行讨论，然后对于每个贴单调队列。

by LiaoYF @ 2022-12-22 11:30:14

@kirihara233 是要开n个单调队列吗，能看看代码吗

by Kevin_Mamba @ 2022-12-22 11:34:12

@Mr_LiaoYifan 建议尽量不用 deque。自己用数组写很方便的。

这和0分应该没关系。

by char_cha_ch @ 2022-12-22 11:43:26

@Mr_LiaoYifan 不用开 n 个。我这里是一个 sort 直接分出每个帖子，并对时间排序。然后在这个全是帖子的地方单调队列。看这里：

#include<cstdio>
#include<algorithm>
#define N 100009

inline int read()
{
    register int ret = 0;
    register bool f = 1;
    register char ch = getchar();
    while (ch < '0' || ch > '9')
        (ch == '-') ? f = 0 : 0, ch = getchar();
    while (ch >= '0' && ch <= '9')
        ret = (ret << 1) + (ret << 3) + (ch ^ 48), ch = getchar();
    return f ? ret : -ret;
}

struct node
{
    int ts, id;
}a[N];

inline bool cmp(node a, node b)
{
    return a.id != b.id ? a.id < b.id : a.ts < b.ts;
}

int q[N];

#include<cstring>

using std::memset;

int main()
{
    register int n = read(), d = read(), k = read(), lst = 1, i, l, r;
    for (i = 1;i <= n;++ i)
        a[i].ts = read(), a[i].id = read();
    std::sort(a + 1, a + 1 + n, cmp);
    for (i = 1;i <= n;++ i)
    {
        memset(q, 0, sizeof q);
        l = 1, r = 0;
        while (a[lst].id == a[i].id)
            ++ i;
        -- i;//获取id全部相等的
        while (lst <= i)
        {
            while (l <= r && a[q[l]].ts + d <= a[lst].ts)//超过范围
                ++ l;
//          printf("%d\n", r - l + 1);
//          printf("%d %d\n", a[lst].ts, a[lst].id);
            if (r - l + 2 >= k)//如果长度大于了
            {
                printf("%d\n", a[i].id);
                lst = i;
            }
            q[++ r] = lst;//已经完全单调了
            ++ lst;//nxt
        }
    }

    return 0;
}

by char_cha_ch @ 2022-12-22 11:44:06

一个 sort 拍过去后已经全部单调了

by Kevin_Mamba @ 2022-12-22 11:50:27

输出的时候为什么循环到 n ？