【题解】日志统计

题目链接：日志统计

算法一

(枚举) 粗略估计 O(n²)

1. 首先这是偏暴力做法，如果出题人想卡也是可以卡掉的。由于第二层循环只在两篇相同文章点赞时刻之差大于等于 D 时，或者遇到两篇编号不同的文章时退出，所以只需要将 N K D 全部设为 1e5 并且所有的文章编号相同，那么该做法就退化到 $O(n^2)$ 了。
2. 将文章编号作为第一关键字，点赞时刻作为第二关键字排序。对于每篇文章的点赞时刻，枚举后续相同文章中点赞时刻之差小于 D 的文章数，如果发现某篇文章符合条件且没有被记录过，则输出该文章编号并记录。

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <map>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;


const int N = 1e5 + 10;

// first编号，second时刻
PII p[N];
int n, d, k;
int cnt[N];
bool st[N];

int main()
{
    cin >> n >> d >> k;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> p[i].second >> p[i].first;
    }

    sort(p + 1, p + n + 1);

    for (int i = 1; i <= n;i ++ )
    {
        cnt[i] = 1;
        for (int j = i + 1; j <= n; j ++ )
        {
            if (p[j].first != p[j - 1].first)
                break;

            if (p[j].second - p[i].second < d) cnt[i] ++;
            else break;
        }

        if (cnt[i] >= k && !st[p[i].first])
        {
            st[p[i].first] = true;
            cout << p[i].first << endl;
        }
    }
    return 0;
}

---

算法二

双指针 线性时间复杂度 O(n)

1. 双指针算法是一种思想，与指针没有关系。这里的双指针是指有两个指向变量指向同一个数组的下标。一般只有具有 单调性 的题目才能用双指针算法。
2. 考虑枚举每一个长度为 D 的时间段，查看当前枚举的时间段内每篇帖子被点赞多少次，记录符合条件的热帖。我们可以发现，由于每个时间段的起点是依次递增的，所以相邻两个时间段只有起点和终点不同，中间有 D - 2 个时刻是重合的，我们可以用 i 指向当前枚举时间段的终点，j 指向当前枚举时间段的起点，每当发现两个时刻之差大于等于 D ，则让 j 向后移动一格。由于 i 和 j 都是单调递增的，所以最多只会遍历两遍，所以时间复杂度是线性的。

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <map>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;


const int N = 1e5 + 10;

// first编号，second时刻
PII p[N];
int n, d, k;
int cnt[N];
bool st[N];

int main()
{
    cin >> n >> d >> k;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> p[i].second >> p[i].first;
    }

    sort(p + 1, p + n + 1);

    for (int i = 1; i <= n;i ++ )
    {
        cnt[i] = 1;
        for (int j = i + 1; j <= n; j ++ )
        {
            if (p[j].first != p[j - 1].first)
                break;

            if (p[j].second - p[i].second < d) cnt[i] ++;
            else break;
        }

        if (cnt[i] >= k && !st[p[i].first])
        {
            st[p[i].first] = true;
            cout << p[i].first << endl;
        }
    }
    return 0;
}