【学校题解】#119. 最大整数题解（2023-08-18更新）

szhiy / 2023-08-18 / 原文

#119. 最大整数题解

本文章的访问次数为次。

Part 1 提示

题目传送门
欢迎大家指出错误并私信这个蒟蒻
欢迎大家在下方评论区写出自己的疑问（记得 @ 这个蒟蒻）
本文已同步至学校网站、博客园。

Part 2 背景

本来是不想写这篇题解的，但是由于卡了这个蒟蒻 $1$ 整天，故此纪念。

Part 3 更新日志

2023-05-26 17:20 文章完成
2023-02-01 17:20 文章同步至学校网站
2023-05-27 18:59 提交审核
2023-05-30 15:22 文章审核通过
2023-07-01 16:04 修改了代码
2023-08-15 21:13 更新了代码格式，使代码看起来更美观
2023-08-18 19:39 更改了文章格式，使文章看起来更加美观
2023-08-18 19:40 文章同步至博客园

Part 4 题目知识点

字符串+贪心

Part 5 题意说明

设有n个正整数（$n<20$），将它们连接成一排，组成一个最大的多位整数。（~~题目简介明了，一看就是出题人懒得写题目背景~~）

Part 6 问题分析

拿到这道题，首先自然会想到大的字符串应该排在前面，因为如果 $A$ 与 $B$ 是两个由数字字符构成的字符串，且 $A$ $>$ $B$ ，一般情况下有 $A+B$ $<$ $B+A$ 的情况。如 $A = $ ' $121$ ', $B=$ ' $12$ '，则 $A + B = $ ' $12112$ '，$B + A = $' $12121$ '，所以 $A + B$ $<$ $B + A$。

为了解决这些问题，根据题意引进另一种字符串比较方法，将 $A + B$ 与 $B + A$ 相比较，如果前者大于后者，则认为 $A > B$ 。按这一定义将所有的数字字符串从大到小排序后连接起来所得到的数字字符串即是这个问题的解。排序时先将所有字符串中的最大值选出来存在数组的第一个元素中，再从第二到最后的一个元素中最大的字符串选出来存在第二个元素中，直到最后的两个元素中选出最大的字符串存在数组的倒数第二个元素为止。

Part 7 代码

// #119. 最大整数
// code by:st20250113
#include <bits/stdc++.h>

using namespace std;

struct num
{
	int a, b;
}c[21];

int n;

int a(int x, int y) // x ^ y
{
	if (y == 0)
	{
		return 1;
	}
	if(y == 1)
	{
		return x;
	}
	int z;
	z = a(x, y / 2); // 这里可以和上面合并写作：int z=a(x,y/2);
	if (y % 2 == 1)
	{
		return z * z * x;
	}
	else
	{
		return z * z;
	}
}

bool abc(num x, num y)
{
	int w, p;
	w = x.a * y.b + y.a;
	p = y.a * x.b + x.a;
	return w > p;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &c[i].a);
		c[i].b = 0;
		int x;
		x = c[i].a; // 这里可以和上面合并写作：int x = c[i].a;
		while (x)
		{
			x /= 10;
			c[i].b++;
		}
		c[i].b = a(10, c[i].b);
	}
	sort(c + 1, c + n + 1, abc);
	for (int i = 1; i <= n; i++)
	{
		printf("%d", c[i].a);
	}
	return 0;
}