UVa10905 Children's Game

不错的贪心题.

方法也很简单, 排个序就行了.

像这样:

bool cmp(const string &lhs, const string &rhs)
{return lhs + rhs < rhs + lhs;}

为什么呢?

首先, 易证满足排序的基础 : 传递性.

其实, 我们能发现, 这个比价函数排出来的序就是这俩的相对位置, 不会改变 (贪心).

如果 lhs + rhs < rhs + lhs, 那么就是说lhs + rhs组成的数大于rhs + lhs;

于是, 就能确定在最终的答案中, 这俩的位置关系肯定就是这样.

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 const int MAXN = 50 + 2;
 7 
 8 int N;
 9 string s[MAXN], ans;
10 
11 bool cmp(const string &lhs, const string &rhs)
12 {return lhs + rhs < rhs + lhs;}
13 
14 int main()
15 {
16     ios::sync_with_stdio(false);
17     while(cin>>N, N)
18     {
19         for(int i = 1; i <= N; i++) cin>>s[i];
20         sort(s + 1, s + N + 1, cmp);
21         ans.clear();
22         for(int i = 1; i <= N; i++)
23             ans = s[i] + ans;
24         cout<<ans<<endl;
25     }
26     return 0;
27 }