放牧代码和思想
专注自然语言处理、机器学习算法
    愛しさ 優しさ すべて投げ出してもいい

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!)n),当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版)》练习题答案

评论 16

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #8

    作者你好。next_permutation() 如果要走遍所有的排列,不是必须先将元素排序吗

    myname8年前 (2016-03-31)回复
    • 友情回复一下,这个题意里面明确说了输入数据是排序好的~(The digits will appear in increasing order…)

      清和7年前 (2017-01-29)回复
  2. #7

    看你的代码能学到很多东西~

    myname8年前 (2016-03-31)回复
  3. #6

    for(int i=0;i<len;i++)
    {
    if(permute&(1<<i)) s1+=s [ i ] ;
    else s2+=s [ i ] ;
    }
    我觉得这个题按照你的思想,不需要使用bitset。只需要有bitset的那个使用思想即可。
    上述我的代码。

    不过还是很感激,学到了很多与string的小知识!

    窗旁的yeben8年前 (2015-12-24)回复
  4. #5

    for(int i=0;i<len;i++)
    {
    if(permute&(1<<i)) s1+=s[i];
    else s2+=s[i];
    }
    我觉得这个题按照你的思想,不需要使用bitset。只需要有bitset的那个使用思想即可。
    上述我的代码。

    不过还是很感激,学到了很多与string的小知识!

    窗旁的yeben8年前 (2015-12-24)回复
  5. #4

    发现自己写不写怎么办

    qingxi曾9年前 (2015-03-07)回复
  6. #3

    我发现我已经无法思考了,想不出来就来看你的题解,简单易懂,我这样会不会变成傻子

    奥特曼9年前 (2015-02-24)回复
    • 不,这是正常的,可以省下很多时间,慢慢来

      hankcs9年前 (2015-02-25)回复
  7. #2

    你好,当测试数据是"0,1,2"时,我们可以知道,(01,2) 或 (02,1) 搭配时有最小值 1 ,但是你得程序输出的是 8,也就是说你的程序认为 (10,2) 搭配时拥有最小值。拿你代码去提交一下,发现竟然AC,可能是它测试数据有漏洞吧~只要把"if (s2[0] == ‘0’ && s2.size() > 1){
    continue; }"删掉就OK了!

    10年前 (2014-10-21)回复
    • 你好,the integer may not start with the digit 0

      hankcs10年前 (2014-10-21)回复
  8. #1

    唉。。我开始的时候用DFS也TLE了。。但关键不是用什么方法,主要是得看出 smallest difference总是产生于长度等于length/2的两个数中。
    我用dfs枚举出所有组合,然后把s1=12 s2=34 和s1=34, s2=12这两种情况重复给去掉了(用DFS枚举,前面一半的组合刚好跟后一半的组合互补,计算组合数目,只处理后一半即可),但还是需要6秒时间才能处理长度为10的输入。

    你似乎木有解决重复的问题,但是用另一种效率更高的优化方法过了TLE。
    如果在解决重复的情况下,再用你的优化方法会更快些,不过数据少的话差别还是不大。

    仕成10年前 (2014-08-12)回复
    • 我算了下,从算法上的确没有解决重复问题,只是位运算优化了暴力搜索而已。

      hankcs10年前 (2014-08-12)回复

我的作品

HanLP自然语言处理包《自然语言处理入门》