题解：P14292 [JOI2024 预选赛 R2] 卡牌游戏 / Card Game 2

· · 题解

分析题目

有 N 张卡牌，每张卡牌上都有一个整数 A_i，其中 1 \le i \le N。判断能否从中选出三张卡牌，选出的三张卡牌从大到小依次为 x,x+3,x+6，x 为某个整数。

代码思路

套三层循环，第二层循环从当前第一层循环的下标加一开始，依次向后枚举，如果当前的数为第一层循环的数加三，则第三层循环从这个数下标加一开始，依次向后枚举。如果当前的数为第二层的数加三，则直接输出 Yes 并结束程序。若三层循环循环完了也没有符合条件的，相当于没有输出 Yes，则输出 No。看不懂可以看一下代码。

for(int i=1;i<=n;++i)
{
    for(int j=i+1;j<=n;++j)
    {
        if(a[j]-a[i]==3)
        {
            for(int q=j+1;q<=n;++q)
            {
                if(a[q]-a[j]==3)
                {
                    cout<<"Yes";
                    return 0;
                }
            }
        }
    }
}
cout<<"No";
return 0;

不过这样时间复杂度为 \mathcal O(n^3)，n 最大为 200 \, 000，很明显会超时，交上去后子任务 2 和 4 都出现了超时，因此需要优化一下代码。

想优化这个代码，可以选择减少无效判断的次数。对此，我们可以先将序列按升序排序，直接使用 sort 即可。当判断时，若这个数减去上一层循环的数大于三时，说明从这个数及以后的数减去上一层循环的数也大于三，因此直接结束这层循环即可。

sort(a+1,a+n+1);
for(int i=1;i<=n;++i)
{
    for(int j=i+1;j<=n;++j)
    {
        if(a[j]-a[i]==3)
        {
            for(int q=j+1;q<=n;++q)
            {
                if(a[q]-a[j]==3)                
                {
                    cout<<"Yes";
                    return 0;
                }
                if(a[q]-a[j]>3) break;
            }
        }
        if(a[j]-a[i]>3) break;
    }
}
cout<<"No";
return 0;

这次代码可以解决子任务 4 的大部分超时，但子任务 2 的超时测试点与上次一样，因此还需优化。

注意到子任务 2 中 1 \le A_i \le 7（1 \le i \le N） ，当数据过小时，会出现很多相同的数，因此还有很多无效判断，因此要对序列进行去重。对于去重，我选择是开一个新数组，当 i=1 或旧数组中当前下标对应的数与前一个数不同，则加入新数组，同时定义新变量存储当前新数组下标，初始为 0，只要有可以加入新数组的数这个变量就加一，加完所有能加的数后该变量还能当作新数组的长度。之后的所有操作都变成对新数组的操作就行了。代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n+5];
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    int b[n+5],l=0;
    for(int i=1;i<=n;++i)
    {
        if(i==1||a[i]!=a[i-1])
        {
            l++;
            b[l]=a[i];
        }
    }
    for(int i=1;i<=l;++i)
    {
        for(int j=i+1;j<=l;++j)
        {
            if(b[j]-b[i]==3)
            {
                for(int q=j+1;q<=l;++q)
                {
                    if(b[q]-b[j]==3)
                    {
                        cout<<"Yes";
                        return 0;
                    }
                    if(b[q]-b[j]>3) break;
                }
            }
            if(b[j]-b[i]>3) break;
        }
    }
    cout<<"No";
    return 0;
}

记录。