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
",ans);
    return 0;
}

  

原文地址:https://www.cnblogs.com/imzscilovecode/p/8888725.html