题目链接：Helvetic Coding Contest 2017 online mirror B. Heidi and Library (medium)
题意：
已知每天的借书序列，你最多能同时保存k种书，现在问你最多要买多少次书，一开始有0种书，超过k种就要扔掉。
题解：
考虑贪心。
首先，显然连续的多天同一种书可以看成存在一天。所以就先将连续重复去掉。
先预处理出每种书所在的位置，当当前的书的种类数大于k时，就扔掉那本下一次出现最晚的书。
然后这个可以用set搞一搞。
1 #include<bits/stdc++.h> 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.x:dis>b.dis;} 9 }; 10 11 int n,k,a[N],ed,now[N],sz; 12 multiset<node>st; 13 vector<int>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 }else 37 { 38 multiset<node>::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 ",ans); 45 return 0; 46 }