[USACO13JAN] Cow Lineup (单调队列,尺取法)

题目链接

Solution

尺取法板子,算是复习一波.

题中说最多删除 \(k\) 种,那么其实就是找一个颜色种类最多为 \(k+1\) 的区间;

统计一下其中最多的颜色出现次数.

然后直接尺取法,然后每次对于 \(col[r]\) 进行统计,时间复杂度 \(O(n)\) .

Code

#include<bits/stdc++.h>

using namespace std;

const int maxn=100008;

int ans;

int n,k,col[maxn];

map <int,int>js;

int main()

{

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++)

    scanf("%d",&col[i]);

    int now=0,l=1,r=0;

    while(r<=n)

    {

        r++;

        if(!js[col[r]])now++;

        js[col[r]]++;

        while(now==k+2)

        {

            js[col[l]]--;

            if(!js[col[l]])now--;

            l++;

        }

        ans=max(ans,js[col[r]]);

    }

    cout<<ans<<endl;

}

巴特西

[USACO13JAN] Cow Lineup (单调队列,尺取法)

题目链接

Solution

Code

最新文章

热门文章