Codeforces 958F2 Lightsabers (medium) 尺取法

时间:2023-03-09 15:52:48
Codeforces 958F2 Lightsabers (medium) 尺取法

题目大意:

输入n,m,分别表示人的个数和颜色的个数,下一行输入n个数,对应每个人的颜色,最后一行输入对应每个颜色的人应有的数量;

问是否能找出一个区间,满足条件但有多余的人,输出多余的人最少的个数,如果连条件都不能满足,输出-1

基本思路:

尺取法,自己写的没有设置l,r标记,也没有用set,一直卡在样例2,之后又卡37,不知道哪里错了,找了很久,后来干脆学习别人的思路吧。

设一个l指针指向当前数列左边,从左往右扫描一遍,将当前颜色记录,

当所有颜色都得到后,进行判断,如果当前l指向的颜色大于需要的颜色,l后移一位,然后更新答案

果然尺取还是应该定义l,r标记的,这样比较好些,也比较好思考;

代码如下:

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<set> using namespace std; typedef long long ll;
typedef long long LL;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const int maxn = 200000+10;
const ll mod = 1e9+9;
set<int>q;
int col[maxn],cnt[maxn],k[maxn];
int main(){
int n,m,sum=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&col[i]);
}
for(int i=1;i<=m;i++){
scanf("%d",&k[i]);
if(k[i]){
q.insert(i);
}
sum+=k[i];
}
int l=1,ans=inf;
for(int r=1;r<=n;r++){
int c=col[r];
++cnt[c];
if(cnt[c]==k[c]){
q.erase(c);
}
if(q.empty()){
while(l<=r&&cnt[col[l]]>k[col[l]]){
--cnt[col[l]];
l++;
}
ans=min(ans,r-l+1-sum);
}
}
if(ans==inf){
ans=-1;
}
printf("%d\n",ans);
return 0;
}