链接:https://ac.nowcoder.com/acm/problem/16783
这个题的贪心方法真的很巧妙。按字符串的"优先级"进行比较,大的放在前面小的放后面。那么问题来了这个优先级是啥?
提前声明一点,字符串string比较大小时,就是按照字典序进行比较的。
优先级是(a>b)吗?
恐怕不是,因为 "9123">"9",如果这样安排的话答案是91239但正确答案是99123
所以真正的优先级是(a+b>b+a),如果(a+b)>(b+a)把a放前面,否则把b放在前面。
举个例子:
n=3 9123 9 8
按照优先级:
9和9123都大于8,又因为99123大于91239所以,
优先级9 9123 8.
#include <iostream> #include <algorithm> #include <sstream> #include <cstring> #include <cstdio> #include <vector> #include <stack> #include <queue> #include <cmath> #include <map> #include <set> #define inf 0xffffff using namespace std; typedef long long ll; bool cmp(string a,string b) { return (a+b)>(b+a); } vector<string>ss; int main() { int n; cin >> n; for(int i=0;i<n;i++) { string tmp; cin >> tmp; ss.push_back(tmp); } sort(ss.begin(),ss.end(),cmp); for(int i=0;i<ss.size();i++) cout << ss[i]; }