题解：P1012 [NOIP 1998 提高组] 拼数

思路 + 证明

这题明显贪心，先把所有数按照字符串输入进来，很容易想到的一个就是按照 return a + b > b + a 来对字符串进行排序。接下来将用一种简单的方式证明为何这种策略是对的。

首先，我们不妨设正整数

a

的位数为

m

，

b

的位数为

n

。那么不难发现将

a

与

b

拼接在一起的最大值就是先

a

后

b

和先

b

后

a

两种拼接方式拼出的最大值，即

a \times 10^n + b

和

b \times 10^m + a

的最大值。那么将

a

和

b

转为字符串。拼接起来也同样两种形式，先

a

后

b

的

a + b

和先

b

后

a

的

b + a

。那么如何比较这两个的大小？显然可以直接比较两个字符串，毕竟越大的数字越靠前，整个数字显然更大。到这里就推出了 a + b > b + a 这一贪心策略。

代码

CPP

//I'm milk dragon
#include<bits/stdc++.h>
const int N = 25;
using namespace std;

string s[N];

bool cmp(string a, string b)
{
    return a + b > b + a;  //套用贪心策略，如果a + b更大，就让 a 排在 b 前面
}

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) 
	{
		cin >> s[i];
	}
	sort(s + 1, s + n + 1, cmp);
	for (int i = 1; i <= n; i++)
	{
		cout << s[i];
	}
	return 0;
}

题解：P1012 [NOIP 1998 提高组] 拼数

文章操作

思路 + 证明

代码

相关推荐

评论

题解：P1012 [NOIP 1998 提高组] 拼数