注意:有反转,请从头看到尾,如果没看完怕你们会误解思路
洛谷原题:https://www.luogu.com.cn/problem/P1012 (没想到这题在洛谷竟然是绿题)
大致思路:排序
思路的确是这样,不可否认,并且思路也很简单
但是,如果你是这么写的话:
那你就错了
注意:这种写法只能在acgo AC,但是在洛谷AC不了,在洛谷只能打 75分
前方高能,正解来袭
正解
一、为什么说上面那种写法不对呢?
我来举个例子:
样例:
2
937 9371
很明显,937 9371 > 9371 937 (打空格方便你们看,输出的时候不用加)
所以说如果按上面的方法来做就不对了,因为9371 的字典序一定比 937大
二、应该如何AC此题?
你看我在上面举例的过程是怎么做的,那正解就应当怎么做
前提 :令第一个数为 x,第二个数为 y,x 放前面是最优解
这里我们会用到字符串贪心里面最经典的一个方法 :邻项交换
顾名思义,就是把相邻的项交换过来,然后比对
很明显这题要我们做的就是邻项交换,所以我们可以得到:
x + y > y + x
得到了这个东西就简单了,废话不多说,上代码
不要复制!