C++(g++ 7.5.0) 解法, 执行用时: 137ms, 内存消耗: 12036K, 提交时间: 2023-01-25 16:18:11

#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
const int N=1e5+5;
int a[N];
map<int,int>la;
map<int,bool>ex;
priority_queue<pair<int,int>>q;
int ne[N];
long long ans;
int main(){
  int n,m;
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    la[a[i]]=1e5+9;
  }
  for(int i=n;i>=1;i--){
    ne[i]=la[a[i]];
    la[a[i]]=i;
  }
  for(int i=1;i<=n;i++){
    if(!ex[a[i]]){
      if(ans>=m){
        ex[a[q.top().second]]=false;
        q.pop();
      }
      ans++;
      ex[a[i]]=true;
    }
    q.push({ne[i],i});
  }
  cout<<ans;
}

Python3 解法, 执行用时: 221ms, 内存消耗: 40420K, 提交时间: 2023-05-14 15:57:03

# 维护的是该元素在下一次出现的最大距离
import heapq

n, m = map(int, input().split())
a = [int(x) for x in input().split()]
# 该元素下一次出现的索引
nxt = [100001]*n
dic = {}
for i, dat in enumerate(a):
    if dat in dic:
        nxt[dic[dat]] = i
    dic[dat] = i
# print(nxt)
# 查询次数，缓存区
cnt, l = 0, 0
hp = []
cache = {}
for i, dat in enumerate(a):
    # 需要访问数据库
    if dat not in cache:
        cnt += 1
        # 缓存还没满
        if l < m:
            l += 1
        else:
            id = heapq.heappop(hp)[1]
            del cache[id]
    cache[dat] = i
    heapq.heappush(hp, (-1*nxt[i], dat))
print(cnt)

C++ 解法, 执行用时: 76ms, 内存消耗: 5880K, 提交时间: 2022-02-16 16:58:08

#include<iostream>
#include<set>
#include<map>
using namespace std;
const int MAX=100005;
int n,m;
int a[MAX];
int las[MAX];
map<int,int> imap;
set<int> iset;
 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	for(int i=1;i<=n;++i)	 
	{
		las[i]=n+1;
		las[imap[a[i]]]=i;
		imap[a[i]]=i;
	}
	int ans=0;
	for(int i=1;i<=n;++i)
		if(iset.find(i)==iset.end()){
			ans++;
			if(iset.size()==m)
				iset.erase(--iset.end());
			iset.insert(las[i]);
		}else{
			iset.erase(i);
			iset.insert(las[i]);
		}
	cout<<ans<<endl;
	
	return 0;
}