P13733 [JOIGST 2025] 扑克 / Poker

lujunxian · 2025-08-18 16:50:02 · 题解

题目传送门

题目大意：有 N 个数进行大小排序并去重，然后如果有K个不重复的数差为 1。就输出 Yes,否则输出 No。 ———————————————————————————
把 N 个数进行大小排序并去重正是桶排序的特点。

RE代码:

#include<bits/stdc++.h>
using namespace std;
int a[3000001];
int main()
{
    int n,k,max=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        a[x]++;
        if(max<x) max=x;
    }
    int s=0;
    for(int i=1;i<max;i++){
        if(a[i]!=0 && a[i+1]!=0)
            s++;
        else s=0;
        if(s==k){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
    return 0;
}

但是会 RE。 因为桶排序不适合数据分布不均情况‌ 。 所以我们可以手动模拟大小排序并去重。（蒟蒻只会模拟）~勿喷~。

AC代码:

#include<bits/stdc++.h>
using namespace std;
int a[90000001];
int b[90000001];
int main()
{
    int n,k,max=0,j=1,N=0,s=1;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>b[i]; 
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++)
        if(max<b[i]){
            a[j]=b[i];
            max=b[i];
            j++;
        }
    for(int i=1;i<=n;i++)
        if(a[i]!=0) N++;

    if(N<k) {
        cout<< "No"<< endl;
        return 0;
    }

    for(int i=1;i<=N;i++){
        if(a[i]!=0 && a[i+1]!=0 && a[i+1]-a[i]==1)
            s++;
        else s=1;
        if(s>=k){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
    return 0;
}

注意：s 要等于 1。

（喜欢的话就点个赞，关个注吧）