首页 > 其他 > 详细

NC16783-拼数

时间:2021-01-20 13:18:40      阅读:17      评论:0      收藏:0      [点我收藏+]

题目链接:https://ac.nowcoder.com/acm/problem/16783

题意:给定n个数,重新排列后构成的数最大

思路:经典贪心

坑点局部最优解是在这个局部选择最优的数放在当前位置,对于两个数来说,最优解应该是l+r>r+l

反思:在贪心排序中要考虑排序的依据如何最方便,比如这题可以根据两个数的同等长度部分的字典序和(较长数的较长部分与较短数的共同部分字符串比较)来作为排序依据,当然更方便的是根据(l+r>r+l)最为方便。 对于所有针对所有元素的贪心题目,都可以去尝试考虑两个相邻的顺序来计算这两个元素作为局部的最优解,同时选择依据可以根据这两个元素lr或者rl来实现。

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string a[25];
bool cmp(string l,string r){
    return l+r>r+l;
}
int main (){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++)
        cout<<a[i];
    return 0;
}

NC16783-拼数

原文:https://www.cnblogs.com/abestxun/p/14302212.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!