数串问题

r囧r小猫 2022-05-11 03:18 238阅读 0赞

**题目描述**

> 设有n个正整数，将他们连接成一排，组成一个最大的多位整数。  
> 如:n=3时，3个整数13,312,343,连成的最大整数为34331213。  
> 如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613。

> **输入描述：** 
> 
>     有多组测试样例，每组测试样例包含两行，第一行为一个整数N（N<=100），第二行包含N个数(每个数不超过1000，空格分开)。
> 
> **输出描述：**
> 
>     每组数据输出一个表示最大的整数。

**示例1**

> **输入**
> 
>     2
>     12 123
>     4
>     7 13 4 246
> 
> **输出** 
> 
>     12312
>     7424613

**原理：**

> **1. 将每个数值的最高位进行比较，大的优先；**
> 
> **2.最高位相同，次高位比较，大的优先，以此类推。**
> 
> **注意：这里利用字符串的比较方法从而很容易得到排序结果，之后将其拼在一起。**
> 
>            这里排序的方法也要稍微修改一下。

#include<iostream>
    #include<string>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    bool DES(string a, string b) { return ((a+b) > (b+a));  }//降序排列方法
    
    int cpystr(vector<string> str)
    {
    	int result = 0;//返回一个数值
    	string temp ;
    	sort(str.begin(), str.end(), DES);
    	for (unsigned int i = 0; i < str.size(); i++)//组合为一个字符串
    	{
    		temp = temp+str[i];		
    	}
    	result = atoi(temp.c_str());//转换为数值，c_str 获取对象的首地址，atoi 字符串到数值的转换
    	return result;
    }
    
    int main()
    {
    	int N;
    	vector<string> str;
    	cout << "Input N:";
    	cin >> N;
    	cout << "input the number:";
        //输入
    	for (int i = 0; i < N; i++)
    	{
    		string temp;
    		cin >> temp;
    		str.push_back(temp);
    	}
    
    	//转换算法
    	cout<<"结果为："<<cpystr(str);
    
    	system("pause");
    	return 0;
    }

**总结：**

> vector<string> str：字符串向量；
> 
> str.push\_back(temp)：将字符串送入向量中，不能用str\[i\]=x形式。
> 
> temp = temp+str\[i\]：字符串连接
> 
> atoi(temp.c\_str())：atoi 字符串到数值的转换