P3419题解

Luo_Saisei · 2025-01-24 23:07:13 · 题解

分析

把这个过程看成这样：

就是对于一个颜色的相邻两次出现位置，你可以对这个区间进行一次线段覆盖并且让答案减少一，并且要求每个整点的覆盖次数不超过给定的一个数，考虑到从左往右扫的时候不用关心当前区间的左端点，为了让后续区间被更少的线段覆盖，拿掉长度最长的线段是必定最优的。

细节

如果有个玩具已经在地上了，可以通过增加容积来实现一次懒更新。

Code

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define int long long
#define fc freopen("in.in", "r", stdin), freopen("out.out", "w", stdout)
const int N = 1e6 + 10;
int a[N];
int cnt[N], pre[N];
int vis[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, k, p;
    cin >> n >> k >> p;
    for (int i = 1; i <= p; i++)
        cin >> a[i];
    for (int i = p; i >= 1; i--)
    {
        if (!cnt[a[i]])
            pre[i] = 1e9;
        else
            pre[i] = cnt[a[i]];
        cnt[a[i]] = i;
    }
    priority_queue<pair<int, int>> pq;
    int ans = 0;
    for (int i = 1; i <= p; i++)
    {
        if (vis[a[i]])
        {
            k++;
            pq.push({pre[i], a[i]});
        }
        else
        {
            if (pq.size() == k)
            {
                vis[pq.top().second]--;
                pq.pop();
            }
            pq.push({pre[i], a[i]});
            vis[a[i]]++;
            ans++;
        }
    }
    cout << ans;
    return 0;
}