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;

}

巴特西

Codeforces 958F2 Lightsabers (medium) 尺取法

最新文章

热门文章