题解：CF802A Heidi and Library (easy)

· · 题解

思路分析

注意到，对于任意一本新书，他会占用一个位置。那么对于他来说有两种决策：要么一直占着坑，等到这本书再一次出现；要么尽早让出来位置。

也就是说，第一种操作等价于在拿到这一本书后开始，一直占据一个空位；第二种操作等价于完全不占据任何空位。

于是问题可以变成这个样子：

我们假定不存在任何书被重新利用，也就是最开始答案为 n，随后我们考虑能不能尽量的重复利用。

首先，为了每一次轮到一个书的时候能有位置，我们必须预留一个空位不用于让书占坑。

然后，每一对 (i,j) 满足 a_i=a_j 且 \forall k\in(i,j),a_k\neq a_i，他需要在 (i,j) 全部占着一个空位才能使得答案减少 1。

于是问题转化成有若干个区间 (i,j)，问你能够从中选择出多少个区间，满足没有任何一个位置被覆盖了 k 次及以上。

显然这就是一个经典的贪心题目了，按照左端点排序，然后如果区间过多了就把右端点最大的部分给丢掉就行了。

参考代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a[500005],ic,lp[500005];
unordered_map<int,int>id; set<int>pq;
vector<int>rp[500005]; int ans;
signed main(){
    ios::sync_with_stdio(0); cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i) id[a[i]]=i;
    for(int i=1;i<=n;++i) a[i]=id[a[i]];
    for(int i=1;i<=n;++i){
        if(lp[a[i]])
            rp[lp[a[i]]+1].emplace_back(i-1);
        lp[a[i]]=i;
    }
    for(int i=1;i<=n;++i){
        for(int v:rp[i]) pq.emplace(v);
        while(pq.size()&&*pq.begin()<i)
            ans++,pq.erase(*pq.begin());
        while(pq.size()>=m) pq.erase(prev(pq.end()));
    }
    cout<<n-ans<<endl;
}