贪心法（一）

久仰大名。没想到这么折腾人。先上定义 ↓

贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心法的特点：
· 不是对所有问题都能得到整体最优解，关键是贪心策略的选择
· 选择的策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

听起来挺简单对吧，但最优解的策略是真不好找，而且往往需要证明（哪怕不太严谨但也应说服自己信任该策略）。下面给出一个例子。

题号：soj 1198 --Substring
题目：给定n个字符串，将其拼接形成一个字典序最小的字符串（1<=n<=8）

那么，我们可以考虑以下几种方案：

• 直接对所有字符串按字典序大小排序后进行拼接。
  
• 暴力枚举所有组合的可能性，再遍历得到字典序最小的组合。
  
• 传说中的贪心法

第一种方案咋一看可行，那么考虑这样一个输入：b、ba；按该方案得到的输出是”bba”，但实际上”bab”才是最优解。所以，存在反例，我们可以否定第一种方案。

显然，暴力枚举是可以得到正确结果的，时间复杂度O(n²)，相对于我们将要讨论的贪心法，既费时又费力。（文末会附上暴力枚举方案的代码）。

那么，在这个题目中贪心法的策略是如何呢？

合理的做法是先对这n个字符串进行某种排序再拼接。这里的排序方式是指，对于两个字符串str1、str2，如果str1+str2 < str2+str1，那么把str1放在str2的前面所得到的字符串就是字典序更小的那个。当每两个字符串之间都按照这个标准进行比较并排序后，最终串起来的结果就是正确答案。

该策略证明如下：

证题：若a <= b，b <= c，那么a <= c(已重载比较符)。
证明：
    由 a <= b 得 ab <= ba； 
    由 b <= c 得 bc <= cb；
    易得 ac <= ca，推出a <= c。证毕。

证明完成，将上述思想转化为代码。

bool cmp(string str1, string str2){
	return str1+str2 < str2+str1;
}

string subStr(int n, string str[]){
	string ret = "";
	sort(str, str+n, cmp);
	for (int i = 0; i < n; ++i){
		ret += str[i];
	}
	return ret;
}

例题写得略长了，之后的题目就点到为止吧。

附录：

求字典序最小的拼接字符串之暴力枚举法