【GOJ 2348】小W与制胡串谜题

传送门

题意

给一些字符串 (s_1,s_2,dots,s_n)，求打乱组合后的 (a_1,a_2,dots,a_n) 使得 (a_1+a_2+dots+a_n) 最小。

正解

就是一道水题，但我就是不会做……

这道题如果要求 (a_1+a_2+dots+a_n) 最小，那么满足他的子集（？）最小，即 (a_n+a_{n+1}+dots+a_m(nle m)) 最小。

那么可以有：如果 (a+b<b+a)，则 (a) 放在 (b) 前面，反之亦然。

然后就没有然后了。

实在是不大清楚怎么写，欢迎大家补充。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
string s[N];
bool cmp(string a,string b) {
	return (a+b)<(b+a);
}
int main() {
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		cin>>s[i];
	}
	sort(s+1,s+n+1,cmp);
	for(int i=1; i<=n; i++) {
		printf("%s",s[i].c_str());
	}
	return 0;
}