0%

PAT甲级REcover the Smallest Number

PAT甲级REcover the Smallest Number

原题

题目

Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given { 32, 321, 3214, 0229, 87 }, we can recover many numbers such like 32-321-3214-0229-87 or 0229-32-87-321-3214 with respect to different orders of combinations of these segments, and the smallest number is 0229-321-3214-32-87.

输入要求

Each input file contains one test case. Each case gives a positive integer N (104) followed by N number segments. Each segment contains a non-negative integer of no more than 8 digits. All the numbers in a line are separated by a space.

输出要求

each test case, print the smallest number in one line. Notice that the first digit must not be zero.

思路

题意很简单,就是给定一个数字段,给他拼成一个最小的数。很容易想到贪心算法,但是贪的是什么?

首先想到按从小到大的顺序输出不就好了嘛,但是仔细想想不是这样的比如321>32但是321放前面才是正确的为什么呢?可以这样想假设我们下一个待选的只有a和b两个,两者是不是你在前我在后就是我在后你在前的关系,那么他们后面的数字位数一定是相同的即总位数-前面的位数-a的位数-b的位数,所以从a开始算两种选择的数字大小如下:

  1. a在前 ab*10^n
  2. b在前 ba*10^n

这样就很容易看出了,决定a和b谁在前面的方法就是比较ab以及ba的大小。

这里可能产生一个疑问,我在每一个位置的选择可不止两种啊,这么多个该怎么比较呢?

有一个巧妙地方法就是借助sort 自己实现一个cmp规则,这样排出的一定符合规则!可以尝试证明一下:

我们假设排完之后的顺序是 a b c d e f…………

使用反证法:如果该顺序不是最优解,那么一定需要通过置换变成最优解,假设我们换了a和c 那么前面从 abc变成了cba(即cba<abc) 而bc<cb bca<cba ab<ba bca<cba<cab同理 一直推到 bca<cba<cab<acb<abc; 两者相悖,所以我们的贪心策略能够得到最优解!

注意输出没有前导零,还有一个测试点需要注意就是结果为0时还要输出0(也就是说不能单纯的不输出前面的0)

AC代码

#include <bits/stdc++.h>
using namespace std;
bool cmp(string a, string b)
{
return a + b < b + a;
}
int main()
{
int n;
cin >> n;
string s[n];
string result;
for (int i = 0; i < n; i++)
{
cin >> s[i];
}
sort(s, s + n, cmp);
for (int i = 0; i < n; i++)
{
result += s[i];
}
int flag = 1;
for (int i = 0; i < result.size() - 1; i++)
{
if (result[i] != '0' || !flag)
{
flag = 0;
cout << result[i];
}
}
cout << result[result.size() - 1];
}