[数据结构与算法]c++实现贪心法构造最大整数问题

c++实现贪心法构造最大整数问题

问题描述：

问题描述：
求给定非负整数序列中的数字排列成的最大数字。
例如：
输入：{50，2，1，9}
输出：95021

思路：

采用贪心算法，先将所有整数转换成字符串，按照ASCII排序，只比较字符串首位字符的ASCII码，比较完成后再将所有字符串拼起来，转换成整数输出。

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <sstream>
using namespace std;

string Int_Str(int a){//调用库函数，实现整数转换成字符串
	stringstream ss;
	ss<<a;
	
	return ss.str(); 
}

bool Cmp(string a,string b){//定义为从大到小排序
	return a>b;
}
int main() {
	int n;
	cout<<"请输入n的值:"<<endl;
	cin>>n;
	int a[n];
	cout<<"请输入n个元素:"<<endl;
	for(int i=0;i<n;i++){
		cin>>a[i];
		
	} 
	string b[n];
	for(int i=0;i<n;i++){
		b[i]=Int_Str(a[i]);
	}
	sort(b,b+n,Cmp);//sort默认是从小到大排序，所以需要自定义排序方式
//	for(int i=0;i<n;i++){
//		cout<<b[i]<<" ";
//	}
	string str="";
	for(int i=0;i<n;i++){
		str+=b[i];
	}
	cout<<str<<endl;
	return 0;
}