题解
1.题意
自己看吧，懒得总结了
2.思路
考虑二分
首先，我们可以先选出我们要的区间，再去进行删数
删数十分好做，第 $i$ 个颜色需要删 $当前第i个数出现次数-k_i$ 次
接下来想一想如何选出最优的区间
我们肯定是希望在每个数出现次数不小于 $k_i$ 的前提下，让区间尽可能的小
那我们可以二分 $n-区间长度$ （主要是在check时要做的是删数后判断是否满足条件）
在每一次check里，我们需要枚举缩区间的时候删的是哪些数
这我们可以动态更新
首先假设当前二分的$mid$是 $x$
所以先假设缩区间删除的是前 $x$ 个数
这我们可以先统计
接下来，把区间变为删前 $x-1$ 个数和最后一个数，可以O(1)更新是否满足条件
然后一直这样往左移动区间，就能统计出是否能够合法了
整体复杂度O(n log n)
3.Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #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++;
}
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++;
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;
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;
}
|