CF818D

jsntzth666 · 2026-05-10 17:20:51 · 题解

CF818D Multicolored Cars 题解

洛谷题目传送门\ Codeforces 题目传送门

第一步题意

我们有 n(1 \le n \le 10^5) 个时刻。第 i 个时刻，会出现数字 a_i(1 \le a_i \le 10^6)。求任意一个数字，满足任意时间，出现过的次数大于等于 m 出现过的次数。

第二步做法

直接暴力是过不去的。

:::info[暴力代码（码风较丑勿喷）]

#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 5;

int n, m, a[N], cnt[N];
set <int> s;

signed main () {
    ios::sync_with_stdio (0), cin.tie (0), cout.tie (0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s.insert (a[i]);
    }

    s.erase (m);

    for (int i = 1; i <= n; i++) {
        cnt[a[i]]++;
        vector <int> del;
        for (auto j : s)
            if (cnt[j] < cnt[m])
                del.push_back (j);
        for (auto j : del)
            s.erase (j);
        if (s.empty ()) {
            cout << "-1\n";
            return 0;
        }
    }

    cout << *s.begin ();
    return 0;
}

:::

我们要考虑优化。

其实判断一个数字是否满足任意时间出现过的次数大于 m 出现过的次数，只需要考虑增加这个数字的时候（还没增加）和所有数字出现完后这个数字出现过的次数是否大于等于 m。

对于这次出现这个数字到下次出现这个数字之前的时间里，这个数字出现次数是不变的，但 m 出现次数是可以变大的，如果下次出现这个数字之前出现过的次数就比 m 出现过的次数大了那这段时间是一定符合的。因此只需要考虑增加的时候和最后。

第三步 AC 代码

:::info[完整代码（码风较丑勿喷）]

#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 5;

int n, m, a[N], cnt[N];
bool ok[N];

signed main () {
    ios::sync_with_stdio (0), cin.tie (0), cout.tie (0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        cnt[a[i]]++;
        if (a[i] == m)
            continue;

        if (cnt[a[i]] == 1)
            ok[a[i]] = 1;

        if (!(cnt[a[i]] > cnt[m])) // 因为已经操作完毕了所以是大于
            ok[a[i]] = 0;
    }

    for (int i = 1; i <= n; i++)
        if (!(cnt[a[i]] >= cnt[m]))
            ok[a[i]] = 0;

    for (int i = 1; i <= 1000000; i++)
        if (ok[i]) {
            cout << i;
            return 0;
        }
    cout << "-1";
    return 0;
}

:::

后记

个人觉得这是一道比较思维的题目，但不至于是蓝题。

制作不易，点个关注，再点个赞吧。

:::info[AI 使用说明] 使用 DeepSeek 润色文章。 :::