题目链接
P10901 [蓝桥杯 2024 省 C] 封闭图形个数 - 洛谷
题目理解
这道题属于自定义排序。数字大小的判断依据是数字中 “封闭图形” 的个数和数值大小。“封闭图形” 就是数字中完全封闭的空间 ，像 0、4、6、9 各有 1 个封闭图形，8 有 2 个，1、2、3、5、7 则没有。
如下图：数字‘798’中共计有3个封闭图形。
比较两个数大小时，先看封闭图形个数，个数多的数大；若个数相同，再比较数值大小，数值大的数大；若封闭图形个数和数值都一样，那这两个数相等。现在要根据这个特殊规则，对给定的 n 个数进行从小到大排序并输出结果。
解题思路
1.获取封闭图形个数
我们先写一个将数字输入其中，可以得到其封闭图形个数的函数。
// 将数字传参，返回值其封闭图形个数
int change(int a)
{
// 封闭图形个数，初始化为0，用于统计数字中封闭图形的数量
int number = 0;
// 用于保存末尾数字，判断封闭图形个数
int last;
// 当数字a大于0时，循环处理每一位数字
while (a > 0)
{
// 取a的个位数字，也就是当前要判断的末尾数字
last = a % 10;
// 如果末尾数字是1、2、3、5、7，这些数字没有封闭图形，不做额外操作
if (last == 1 || last == 2 || last == 3 || last == 5 || last == 7)
{
}
// 如果末尾数字是8，8有2个封闭图形，所以将封闭图形个数number增加2
else if (last == 8)
{
number += 2;
}
// 其他情况，即末尾数字是0、4、6、9，这些数字都有1个封闭图形，将number增加1
else
{
number++;
}
// 去掉a的个位数字，以便处理下一位数字
a /= 10;
}
// 返回统计得到的封闭图形个数
return number;
}2.比较该规则下两个数的大小
根据蓝桥王国的规则，整数
a大于整数b需满足以下两个条件之一：
- 封闭图形个数优先：
a的封闭图形个数大于b的封闭图形个数。在代码中，通过change(a) > change(b)来判断。这里change函数用于获取一个数的封闭图形个数，若a的封闭图形个数比b多，那么依据规则a更大。- 封闭图形个数相同比数值：当
a和b的封闭图形个数相等时，比较它们本身的数值大小，若a的数值大于b的数值，则a更大。在代码中体现为change(a) == change(b) && a > b，即先判断两者封闭图形个数相等，再判断a的数值大于b。
//判断a和b的大小
int judge(int a,int b)
{
//此时a的封闭图形个数>b的封闭图形个数
if((change(a)>change(b))||(change(a)==change(b)&&a>b))
{
return 1;
}
else
{
return 0;
}
}3.排序
先用大家都熟知的冒泡排序：
//交换函数
void swap(int* a,int* b)
{
int c;
c=*a;
*a=*b;
*b=c;
}
//冒泡排序
void BubbleSort(int arr[],int n)
{
int i,j;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
if(judge(arr[j],arr[j+1])==1)
{
swap(&arr[j],&arr[j+1]);
}
}
}
}完整代码（冒泡排序）
#include <stdio.h>
//将数字传参，返回值其封闭图形个数
int change(int a)
{
//封闭图形个数
int number=0;
//用于保存末尾数字，判断封闭图形个数
int last;
while(a>0)
{
last=a%10;
if(last==1||last==2||last==3||last==5||last==7)
{
}
else if(last==8)
{
number+=2;
}
else
{
number++;
}
a/=10;
}
return number;
}
//交换函数
void swap(int* a,int* b)
{
int c;
c=*a;
*a=*b;
*b=c;
}
//判断a和b的大小
int judge(int a,int b)
{
//此时a的封闭图形个数>b的封闭图形个数
if((change(a)>change(b))||(change(a)==change(b)&&a>b))
{
return 1;
}
else
{
return 0;
}
}
//冒泡排序
void BubbleSort(int arr[],int n)
{
int i,j;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
if(judge(arr[j],arr[j+1])==1)
{
swap(&arr[j],&arr[j+1]);
}
}
}
}
main()
{
int n;
scanf("%d",&n);
int arr[n];
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
BubbleSort(arr,n);
for(int i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
}此时我们会发现，当数据规模过大时，会超出时间限制。
下面我们用快排：
完整代码（快速排序）
#include <stdio.h>
//将数字传参，返回值其封闭图形个数
int change(int a)
{
//封闭图形个数
int number = 0;
//用于保存末尾数字，判断封闭图形个数
int last;
while (a > 0)
{
last = a % 10;
if (last == 1 || last == 2 || last == 3 || last == 5 || last == 7)
{
}
else if (last == 8)
{
number += 2;
}
else
{
number++;
}
a /= 10;
}
return number;
}
//交换函数
void swap(int* a, int* b)
{
int c;
c = *a;
*a = *b;
*b = c;
}
//判断a和b的大小
int judge(int a, int b)
{
//此时a的封闭图形个数>b的封闭图形个数
if ((change(a) > change(b)) || (change(a) == change(b) && a > b))
{
return 1;
}
else
{
return 0;
}
}
// 分区函数，用于将数组 a 中从 left 到 right 区间的元素按照基准值进行划分
// 返回值为基准值最终所在的位置
int _QuickSort(int* a, int left, int right) {
// 选择最左边的元素作为基准值的索引
int keyi = left;
// 左指针从基准值的下一个位置开始
++left;
// 当左指针小于等于右指针时，继续进行分区操作
while (left <= right) {
// 从右向左找小于基准值的元素
// 当右指针指向的元素大于基准值，并且左指针小于等于右指针时，右指针向左移动
while (left <= right && judge(a[right], a[keyi]) == 1) {
--right;
}
// 从左向右找大于基准值的元素
// 当左指针指向的元素小于基准值，并且左指针小于等于右指针时，左指针向右移动
while (left <= right && judge(a[left], a[keyi]) == 0) {
++left;
}
// 如果左指针仍然小于等于右指针，说明找到了需要交换的元素对
if (left <= right) {
// 交换左指针和右指针所指向的元素
// 交换完成后，左指针右移一位，右指针左移一位
swap(&a[left++], &a[right--]);
}
}
// 当左右指针相遇后，将基准值与右指针所指向的元素交换位置
// 此时右指针所在的位置就是基准值最终应该所在的位置
swap(&a[keyi], &a[right]);
// 返回基准值最终所在的位置，用于后续递归排序
return right;
}
// 封装的快速排序函数，递归调用 _QuickSort 函数
void QuickSort(int* a, int left, int right) {
if (left < right) {
// 调用 _QuickSort 函数进行分区，得到基准值的最终位置
int key = _QuickSort(a, left, right);
// 递归对基准值左边的子数组进行排序
QuickSort(a, left, key - 1);
// 递归对基准值右边的子数组进行排序
QuickSort(a, key + 1, right);
}
}
int main()
{
int n;
scanf("%d", &n);
int arr[n];
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
QuickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
return 0;
} 不会快排的同学移步下文：
AC拿捏！
———（如有问题，欢迎评论区提问）———