题目: [NOIP1998]拼数 ,哈哈,我们今天来看一道稍微简单的贪心题吧,这是选自NOIP提高组的一道题,好了,我们一起来看看题意吧:
题目描述是复制的,可能有部分显示不对,我就把题目链接放下面!
题目链接: [NOIP1998]拼数
题目描述
设有n个正整数(n ≤ 20),将它们联接成一排,组成一个最大的多位整数。 例如:n=3时,3个整数13,312,343联接成的最大整数为:34331213 又如:n=4时,4个整数7,13,4,246联接成的最大整数为:7424613
输入描述
第一行,一个正整数n。
第二行,n个正整数。
输出描述
一个正整数,表示最大的整数
示例1
输入
3
13 312 343
输出
34331213
思路
:
这道题采用贪心的思想,非常巧妙,具体的我们看看代码,有注释额!
我们来看看成功AC的代码吧:
#include<bits/stdc++.h> using namespace std; string s[100]; int n; bool cmp(string s1,string s2){ return s1+s2>s2+s1;//按照这个顺序排序,非常巧妙, //假设s1=321,s2=32;s1+s2=32132,s2+s1=32321这样下面sort排下来就是32>321 } int main(){ cin.tie(0);cout.tie(0); ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) cin>>s[i]; sort(s+1,s+1+n,cmp);//排序好了就是答案 for(int i=1;i<=n;i++) cout<<s[i]; return 0; }