题解：P14131 【MX-X22-T2】「TPOI-4B」K Problem

qkj_qwq · 2025-10-02 21:56:56 · 题解

解题思路

模拟，把所以可能的 k 都列举一遍。

可以得出这个区间的长度 len=\dfrac{k\times(k+1)}2。然后，对于所有长度为 len 的区间判断元素个数是否合法。注意，这里的枚举区间的元素个数必须像滑动窗口一样，右边进左边出，否则会导致时间复杂度过大。

这里的 k 的最大值在 450 以下（因为 \dfrac{450\times451}2>10^5）。我在赛时直接使 k=\max\limits_{i=1}^na_i，痛失 \text{20 pts}。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100010],b[100010],n;
bool pd(int mid)
{
    for(int i=1;i<=mid;i++)
        if(b[i]!=i)return 0;
    return 1;
}
bool ck(int x)
{
    memset(b,0,sizeof b);
    int len=(x+1)*x/2;
    for(int i=1;i<=n;i++)
    {
        b[a[i]]++;
        if(i>len)b[a[i-len]]--;
        if(i>=len&&pd(x))return 1;
    }
    return 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    BREAK:
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=450;i>=1;i--)
            if(ck(i))
            {
                cout<<i<<'\n';
                goto BREAK;
            }
        cout<<"0\n";
    }
    return 0;
}