传送门

题意

给一些字符串 \(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(n\le 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;
}