Educational Codeforces Round 170 (Rated for Div. 2) C. New Games

Yorg / 2024-10-17 / 原文

题意转化

找一些相邻的数(其中相邻定义为递增序下任意相邻两数差 $\leq 1$)
求相邻数中, 不同数字有 $k$ 种, 取到数字个数的最大值

算法

容易想到按顺序排列
观察到有点像滑动窗口, 考虑用队列维护一个出现不同数字次数为 $k$ 的区间, 再计算

代码

来自转载地址

void solve()
{
    int n,k;
    cin>>n>>k;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a.begin()+1,a.end());
    queue<int> q;
    map<int,int> num;
    int ans=0,cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(q.empty())
        {
            q.push(a[i]);
            num[a[i]]++;
            cnt++;
            ans=max(ans,(int)q.size());
        }
        else
        {
            if(q.back()==a[i])
            {
                q.push(a[i]);
                num[a[i]]++;
                ans=max(ans,(int)q.size());
            }
            else
            {
                if(a[i]==q.back()+1)
                {
                    q.push(a[i]);
                    num[a[i]]++;
                    cnt++;
                    while(q.size() && cnt>k)
                    {
                        int x=q.front();q.pop();
                        num[x]--;
                        if(!num[x]) cnt--;
                    }
                    ans=max(ans,(int)q.size());
                }
                else
                {
                    while(q.size())
                    {
                        int x=q.front();q.pop();
                        num[x]--;
                        if(num[x]==0) cnt--;
                    }
                    q.push(a[i]);
                }
            }
        }
    }
    cout<<ans<<endl;
}