题目链接：

题意：

已知每天的借书序列，你最多能同时保存k种书，现在问你最多要买多少次书，一开始有0种书，超过k种就要扔掉。

题解：

考虑贪心。

首先，显然连续的多天同一种书可以看成存在一天。所以就先将连续重复去掉。

先预处理出每种书所在的位置，当当前的书的种类数大于k时，就扔掉那本下一次出现最晚的书。

然后这个可以用set搞一搞。

1 #include
      
        2 #define F(i,a,b) for(int i=(a);i<=(b);++i) 3 using namespace std; 4  5 const int N=4e5+7; 6 struct node{ 7     int x,dis; 8     bool operator <(const node &b)const{
    return dis==b.dis?x
       
        b.dis;} 9 };10 11 int n,k,a[N],ed,now[N],sz;12 multiset
        
         st;13 vector
         
          nxt[N];14 int cnt[N];15 16 int main(){17     int ans=0;18     scanf("%d%d",&n,&k);19     F(i,1,n)scanf("%d",a+i);20     ed=1;21     F(i,2,n)if(a[i]!=a[ed])a[++ed]=a[i];22     F(i,1,n)nxt[a[i]].push_back(i);23     F(i,1,n)nxt[i].push_back(N);24     F(i,1,ed)25     {26         if(now[a[i]]==0)27         {28             now[a[i]]=1;sz++;29             ans++;30             if(sz>k)31             {32                 now[(*st.begin()).x]=0;33                 st.erase(st.begin());34                 sz--;35             }    36         }else37         {38             multiset
          
           ::iterator it;39             it=st.lower_bound({a[i],i});40             st.erase(it);41         }42         st.insert({a[i],nxt[a[i]][++cnt[a[i]]]});43     }44     printf("%d\n",ans);45     return 0;46 }