题目 ：(https://www.xinyoudui.com/ac/contest/747003D8300053402101126/problem/9504)
code:
#include <bits/stdc++.h>
using namespace std;
const int M = 1e6+1;
int n, m, a[M], chg[M], ans, num;
struct Page {
int time, cnt;
friend bool operator< (Page x, Page y) {
return x.cnt == y.cnt ? x.time > y.time : x.cnt > y.cnt;
}
};
priority_queue<Page> pq;
int tmp[M];
void discretizing() {
memcpy(tmp, a, sizeof a);
sort(tmp+1, tmp+m+1);
int k = unique(tmp+1, tmp+m+1)-tmp-1;
for (int i = 1; i <= m; ++i)
a[i] = lower_bound(tmp+1, tmp+k+1, a[i])-tmp;
}
int main() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= m; ++i)
cin >> a[i];
discretizing();
for (int i = 1; i <= m; ++i) {
if (chg[a[i]]) chg[a[i]]++, ans++;
if (!chg[a[i]]) {
if (num < n) chg[a[i]]=1, num++;
if (num == n) {
auto cur = pq.top(); pq.pop();
chg[a[i]]++, chg[a[cur.time]] = 0;
}
pq.push({i, chg[a[i]]});
}
}
cout << ans;
return 0;
}