题解
1.题意
自己看吧，懒得总结了
2.思路
考虑二分
首先，我们可以先选出我们要的区间，再去进行删数
删数十分好做，第 \(i\) 个颜色需要删 \(当前第i个数出现次数-k_i\) 次
接下来想一想如何选出最优的区间
我们肯定是希望在每个数出现次数不小于 \(k_i\) 的前提下，让区间尽可能的小
那我们可以二分 \(n-区间长度\) （主要是在check时要做的是删数后判断是否满足条件）
在每一次check里，我们需要枚举缩区间的时候删的是哪些数
这我们可以动态更新
首先假设当前二分的\(mid\)是 \(x\)
所以先假设缩区间删除的是前 \(x\) 个数
这我们可以先统计
接下来，把区间变为删前 \(x-1\) 个数和最后一个数，可以O(1)更新是否满足条件
然后一直这样往左移动区间，就能统计出是否能够合法了
整体复杂度O(n log n)
3.Code
#include<bits/stdc++.h>using namespace std;
int n,m,k[200010],a[200010],cnt[200010],vis[200010],temp[200010],anscnt[200010];
int check(int x){int flag=0;for(int i=1;i<=n;i++)temp[a[i]]=cnt[a[i]];for(int i=1;i<=x;i++){cnt[a[i]]--;if(cnt[a[i]]==k[a[i]]-1)flag++;}//cout<<flag<<";\n";if(flag==0)return 1;for(int i=1;i<=x;i++){cnt[a[x-i+1]]++;if(cnt[a[x-i+1]]==k[a[x-i+1]])flag--;cnt[a[n-i+1]]--;if(cnt[a[n-i+1]]==k[a[n-i+1]]-1)flag++;//cout<<flag<<";\n";if(flag==0)return 1;}return 0;
}
main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i],cnt[a[i]]++,anscnt[a[i]]++;for(int i=1;i<=m;i++)cin>>k[i];for(int i=1;i<=m;i++){if(k[i]>cnt[i]){cout<<-1;return 0;}}int l=1,r=n;while(l<=r){int mid=(l+r)>>1;//cout<<mid<<endl;if(check(mid)){l=mid+1;for(int i=1;i<=n;i++)anscnt[a[i]]=cnt[a[i]];for(int i=1;i<=n;i++)cnt[a[i]]=temp[a[i]];}else{r=mid-1;for(int i=1;i<=n;i++)cnt[a[i]]=temp[a[i]];}}int ans=0;for(int i=1;i<=n;i++){if(anscnt[a[i]]!=-1){ans+=anscnt[a[i]]-k[a[i]];anscnt[a[i]]=-1;}}cout<<ans;return 0;
}