蓝桥杯历届真题 # 封闭图形个数(C++,Java)

题目解读

题目链接

[蓝桥杯 2024 省 C] 封闭图形个数

题目描述

在蓝桥王国，数字的大小不仅仅取决于它们的数值大小，还取决于它们所形成的“封闭图形”的个数。

封闭图形是指数字中完全封闭的空间，例如数字$1$、$2$、$3$、$5$、$7$ 都没有形成封闭图形，而数字 $0$、$4$、$6$、$9$ 分别形成了 $1$ 个封闭图形，数字 $8$ 则形成了 $2$ 个封闭图形。值得注意的是，封闭图形的个数是可以累加的。例如，对于数字 $68$，由于 $6$ 形成了 $1$ 个封闭图形，而 $8$ 形成了 $2$ 个，所以 $68$ 形成的封闭图形的个数总共为 $3$。

在比较两个数的大小时，如果它们的封闭图形个数不同，那么封闭图形个数较多的数更大。例如，数字 $41$ 和数字 $18$，它们对应的封闭图形的个数分别为 $1$ 和 $2$，因此数字 $41$ 小于数组 $18$。如果两个数的封闭图形个数相同，那么数值较大的数更大。例如，数字 $14$ 和数字 $41$，它们的封闭图形的个数都是 $1$，但 $14<41$，所以数字 $14$ 小于数字 $41$。如果两个数字的封闭图形个数和数值都相同，那么这两个数字被认为是相等的。

小蓝对蓝桥王国的数字大小规则十分感兴趣。现在，他将给定你 $n$ 个数 $a_1,a_2,\cdots ,a_n$，请你按照蓝桥王国的数字大小规则，将这 $n$ 数从小到大排序，并输出排序后结果。

输入格式

输入的第一行包含一个整数 $n$，表示给定的数字个数。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots ,a_n$，相邻整数之间使用一个空格分隔，表示待排序的数字。

输出格式

输出一行包含 $n$ 个整数，相邻整数之间使用一个空格分隔，表示按照蓝桥王国的数字大小规则从小到大排序后的结果。

样例 #1

样例输入 #1

3
18 29 6

样例输出 #1

6 29 18

提示

【样例说明】

对于给定的数字序列 $[18,29,6]$，数字 $18$ 的封闭图形个数为 $2$，数字 $29$ 的封闭图形个数为 $1$，数字 $6$ 的封闭图形个数为 $1$。按照封闭图形个数从小到大排序后，得到 $[29,6,18]$。

由于数字 $29$ 和数字 $6$ 的封闭图形个数相同，因此需要进一步按照数值大小对它们进行排序，最终得到 $[6,29,18]$。

【评测用例规模与约定】

对于 $50\%$ 的评测用例，$1\le n\le 2\times 10^3$，$1\le a_i\le 10^5$。
对于所有评测用例，$1\le n\le 2\times 10^5$，$1\le a_i\le 10^9$。

思路

按照比较规则手写排序即可

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N =2e5+10;

struct arr{
    int num;
    int cnt;
}arr[N];

int check(int n){
    int cnt=0;
    while(n){
        int temp=n%10;
        if(temp==0 || temp==4 || temp==6 || temp==9)cnt++;
        else if(temp==8)cnt+=2;
        n/=10;
    }
    return cnt;
}

bool cmp(struct arr x, struct arr y) {
    //如果cnt一样大,那么就比较num -- 升序排序
    if (x.cnt == y.cnt)return x.num < y.num;
    //否则优先比较 cnt的大小
    else return x.cnt < y.cnt;
}

int main(){
    int n;
    scanf("%d",&n);

    for(int i=0; i<n; i++){
        int num;
        scanf("%d",&num);
        //统计封闭图形个数
        int cnt=check(num);
        arr[i]={num,cnt};
    }

    sort(arr,arr+n,cmp);

    for(int i=0; i<n; i++)printf("%d ",arr[i].num);
}

import java.util.*;


class Arr{
    int num;
    int cnt;

    Arr(int num, int cnt) {
        this.num = num;
        this.cnt = cnt;
    }

}

class Main{
    static Scanner sc =new Scanner(System.in);
    static final int N = 200010;
    static Arr[] arr = new Arr[N];
    public static void main(String args[]) {
        int n =sc.nextInt();
        for(int i=0; i<n; i++){
            int num=sc.nextInt();
            int cnt=check(num);
            arr[i]=new Arr(num,cnt);
        }
        Arrays.sort(arr,0,n,cmp);

        for(int i=0; i<n; i++){
            System.out.println(arr[i].num+" ");
        }
    }

    static int check(int n){
        int cnt=0;
        while(n>0){
            int temp=n%10;
            if(temp==0 || temp==4 || temp==6 || temp==9)cnt++;
            else if(temp==8)cnt+=2;
            n/=10;
        }
        return cnt;
    }

    static Comparator<Arr> cmp = new Comparator<Arr>() {
        @Override
        public int compare(Arr x,Arr y){
            if(x.cnt==y.cnt)return Integer.compare(x.num, y.num);
            else return Integer.compare(x.cnt, y.cnt);
        }
    };
}

🌻编写本篇文章目的是笔者想以输出的形式进行学习，顺便记录学习点滴🌻

🌹 如果本篇文章对你有帮助的话那就点个赞吧👍🌹

😇 本篇文章可能存在多处不足，如有修改意见，可以私信或者评论我哦 😇