POJ 2718 Smallest Difference 《挑战程序设计竞赛(第2版)》练习题答案

2.1 最基础的“穷竭搜索” 穷竭搜索

POJ 2718 Smallest Difference

将一个数切一刀拆成两个数，两个数每一位数字的顺序都可改变，但是不能有前导0。求这两个数之差的最小值。

我使用了搜索并且避免了递归，自认为是比较好的算法。

一开始我想到的是枚举，并且很快给出了实现：

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n;
    cin >> n;
    cin.ignore();
    while (n--)
    {
        string all;
        getline(cin, all);
        all.erase(remove(all.begin(), all.end(), ' '), all.end());
        int result = 0x3F3F3F3F;
        int cut = all.size() / 2;
        do 
        {
            string s1 = all.substr(0, cut);
            string s2 = all.substr(cut);
            if ((s1[0] == '0' && s1.size() > 1) ||
                (s2[0] == '0' && s2.size() > 1)
                )
            {
                continue;
            }
            int n1 = atoi(s1.c_str());
            int n2 = atoi(s2.c_str());
            int dif = abs(n1 - n2);
            if (dif < result)
            {
                result = dif;
            }
        } while (next_permutation(all.begin(), all.end()));
		
        cout << result << endl;
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

没料到TLE，后来想了想，这里的复杂度是O((length!)ⁿ)，当length = 10 的时候内层最高达到了3628800 次循环，而用例则可能是很多的。

要优化得下点功夫，起先想到改用模拟的方法，分奇偶讨论，可是这道题目是放在2.1 最基础的“穷竭搜索” 穷竭搜索这节里，目的是训练搜索算法。

于是继续走搜索的路线，上面的程序之所以慢，是因为重复计算。比如第一个字串为12，第二个字串为34这种情况和第一个字串为34，第二个字串为12这种情况被视作不同的情况。这是应当被优化的第一个点。

第二个点是string类型的全排操作比较费时，可以用位运算优化。

我看到有些人用dfs递归，感觉很别扭，代码一不好理解，二浪费栈。

我使用了我最喜欢的玩具bitset：

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <string>
#include <algorithm>
#include <bitset>
using namespace std;

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n;
	cin >> n;
	cin.ignore();
	while (n--)
	{
		string all;
		getline(cin, all);
		all.erase(remove(all.begin(), all.end(), ' '), all.end());
		int length = all.size();
		int cut = length / 2;
		int permute = 1 << length;
		int result = 0x3F3F3F3F;
		do
		{
			bitset<10> used = static_cast<bitset<10>>(permute);
			string s1, s2;
			for (int i = 0; i < length; ++i)
			{
				if (used[i])
				{
					s1 += all[i];
				}
				else
				{
					s2 += all[i];
				}
			}
			if (s1.size() != cut)
			{
				continue;
			}
			if (s1[0] == '0' && s1.size() > 1)
			{
				continue;
			}
			// s1 s2 已经被切割出来了
			// 穷举它们
			do
			{
				int n1 = atoi(s1.c_str());
				do
				{
					if (s2[0] == '0' && s2.size() > 1)
					{
						continue;
					}
					int n2 = atoi(s2.c_str());
					int dif = abs(n1 - n2);
					//cout << s1 << ' ' << s2 << " dif " << dif << " result: " << result << endl;
					if (dif < result)
					{
						result = dif;
					}
				} while (next_permutation(s2.begin(), s2.end()));
			} while (next_permutation(s1.begin(), s1.end()));
		} while (--permute);

		cout << result << endl;
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2718 Smallest Difference 《挑战程序设计竞赛(第2版)》练习题答案