SOJ--1117: 最大整数

￡神魔★判官ぃ 2022-08-26 08:12 211阅读 0赞

# 1117: 最大整数 #

**【问题描述】**

设有n个正整数,将他们连接成一排,组成一个最大的多位整数.

例如:n=3时,3个整数13,312,343,连成的最大整数为:34331213

又如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613

**【输入】**

第1行一个正整数L,代表测试数据的组数。

接下来L行，每行第一个是正整数N（1<=N<=6）,该行接下来有N个正整数Mi（1<=Mi<=3000）

**【输出】**

输出L行，每组输入数据输出一行，输出连接成的最大多位数

**【样例输入】**

2  
3 13 312 343  
4 7 13 4 246

**【样例输出】**

34331213  
7424613

解析：贪心问题，如果暴力模拟的话比较麻烦，要考虑位数，还要每一位进行比较，这道题其实考察的是近似排序，直接排序就好了，具体如下，很显然应该按字符串进行输入，对于输入的字串a和b比较ab和ba的大小，如果ab大的话则定义a>b，反之b>a，直接利用STL中的sort(vStr.begin(),vStr.end(),cmp)自定义cmp函数就ok了，这样就简单多了哈！

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <string>
    using std::endl;
    using std::cout;
    using std::cin;
    using std::sort;
    using std::vector;
    using std::string;
    //排序规则
    bool cmp(string str1 , string str2)
    {
    	string temp1 = str1+str2;
    	string temp2 = str2+str1;
    	return temp1>temp2;
    }
    int main()
    {
    	vector<string> vStr;
    	string str;
    	int L , N;
    	cin >> L;
    	while(L--)
    	{
    		vStr.clear();
    		cin >> N;
    		for(int i=0; i<N; ++i)
    		{
    			cin >> str;
    			vStr.push_back(str);
    		}
    		sort(vStr.begin() , vStr.end() , cmp);
    		//输出
    		for(int i=0; i<N; ++i)
    		{
    			cout << vStr[i];
    		}
    		cout << endl;
    	}
    	return 0;
    }

如果有不正确的地方，请提出您的建议，请批评指正哈！