当前位置:首页 > 算法 > 正文内容

【贪心】----(字典序)最大整数

亿万年的星光4年前 (2021-02-06)算法2458

【题目描述】

      设有n个正整数(n≤20),将它们联接成一排,组成一个最大的多位整数。

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

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

【输入】

       两行,第一行n。表示有n个数。

       第二行是 n个数。

【输出】

连接成的多位数

【输入样例】


3
13 312 343


【输出样例】


34331213

【题目分析】

 1.字符串排序的规则:首先按字典序,然后看串长度。如7>414 321>32

 2.



【贪心思路】

使用贪心思想,首先把每两个数进行一次组合,把组合过后较大的那个结果的前面那个数排在前面,后面的那个数排在后面;以此类推之后,最后就能得出n个数组合的最大值。

【解题思路】

第一种方法是使用结构体来存放输入数字的大小和长度,类型都是整形,但是两个整形的数组合起来比较麻烦,比如说两个整数a和b,长度分别为lena和lenb,组合数为a*10^lenb+b和b*10^lena+a,比较这两个数的大小,比较麻烦;

例如13 和312 两个组合成   不同数字,可以是

13312和31213

组合过程可以用13*10^3+312  和 312*10^2+13

 第二种方法我使用字符串来存放输入的数字,字符串组合就比较简单了,同样两个数字a和b,不用考虑两个字符串的长度,字符串组合直接使用加符号,所以组合数为a+b和b+a,比较大小也可以直接比较(return a+b>b+a?a+b:b+a),是不是比整形方法的简单。


【参考代码1】

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct num {
	long long x,y;//x表示这个数字,y表示这个数字的长度
} v[25];
int comp(num a,num b) {
	return a.x*pow(10,b.y)+b.x>b.x*pow(10,a.y)+a.x;//每两个数进行组合,找出最大的数字排列顺序
}
int main() {
	int n,temp,len=0; //n个数,临时变量, 长度 
	cin>>n;  //n个数 
	for(int i=1; i<=n; i++) {
		cin>>v[i].x; //读入这个数 
		temp=v[i].x; //把这个数赋值给临时变量 
		len=0; //长度初始化 
		while(temp) { //计算这个数字的长度
			len++;
			temp/=10;
		}
		v[i].y=temp; //把长度赋值给结构体 
	}
	sort(v+1,v+1+n,comp);  //结构体排序 
	for(int i=1; i<=n; i++) 
		cout<<v[i].x;   //输出 
	return 0;
}


【参考代码2】

#include<iostream>
#include<algorithm>
using namespace std;
int cmp(string a,string b)//定义字符串排序
{
    if(a+b>b+a)return 1;
         else return 0;
}
int main()
{
  int n;
  string a[25];
  cin>>n;
  for(int i=1;i<=n;i++)
      cin>>a[i];
  sort(a+1,a+1+n,cmp);
  for(int i=1;i<=n;i++)
      cout<<a[i];
  return 0;
}


【问题】:

为什么 cmp函数里不直接写 return a>b?
例如下面的例子:

1 10

这两个数如果用字典序排列,那么10>1 。这样组合出来的数据是101。很明显这样组合不是最大的,最大的组合应该是110。所以,直接按照字典序排序是不对的,我们需要将数据进行两两组合,最后看结果。

101 和110的字典序相比,明显110的字典序更大。





扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【排序】----选择排序

【排序】----选择排序

1.基本思想每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在待排序的数列最前,直到全部待排序的数据排完。2.过程首先初始化最小元素索引值为首元素。依次遍历待排序数列,遇到小于该最小索引...

【算法】高精度(2)

五、高精度处理进位与借位    其实也很简单,我们再来模拟一下,1439+887的时候,首先我们最低位相加,得到16,那么答案最低位就是6,再进个1,然后两数的十位相加,...

【算法】单调栈

一、单调栈单调栈(Monotonic Stack)是一种特殊的栈结构,其核心思想是维护栈内元素的单调性(单调递增或单调递减)。单调栈通常用于解决与元素大小关系相关的问题,例如:找到数组中每个元素的下一...

【算法】动态规划(二)——数字三角形问题

【算法】动态规划(二)——数字三角形问题

1.问题描述及状态定义数字三角形问题:有一个非负整数组成的三角形,第一行只有一个数,除了最下行之外每个数字的坐下方和右下方各有一个数。如下图所示:从第一行开的数开始走,每次可以往下或右走一格,直到走到...

【二分】----基础用法

【二分】----基础用法

0.二分法简介二分法是一种查找算法要求:数据必须是有序序列核心思想:掐头去尾取中间1. 引入对于一个有序数组,如{1,3,6,8,23,56,78,99},如果我们要查找其中的一个数78的下标位置,按...

【算法】滑动窗口1—窗口大小固定

【算法】滑动窗口1—窗口大小固定

一、定义滑动窗口算法(Sliding Window Algorithm)是一种用于解决数组或字符串中子数组或子串问题的优化技术。它通过维护一个窗口(通常是数组或字符串的一个连续子区间),在遍历过程中动...