PKU 2718-Smallest Difference

PKU

問題概要

互いの異なる数字（０〜９)が与えられる．
その数値を並べて二つの数字を作るとき，その二つの数値の差の最小値を求めよ．
例：1 2 3の場合12-3=9

解法

全探索（数値の個数<=4)

  • 書くだけ

最良優先探索(数値の個数>4)

  • 最良の場合の差が小さい順に探索

実装(C++)

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <set>
#include <queue>
using namespace std;
int pow10[]={1,10,100,1000,10000,100000};
int n,digits[10];

typedef pair<int,int> P;
struct State{
	int a,b;
	int used;
	int max_dist;
	int min_dist;
	int k;
	State(int a,int b,int used,int k):a(a),b(b),used(used),k(k){
		max_dist=(a-b)*pow10[k]+pow10[k]-1;
		min_dist=(a-b)*pow10[k]+1-pow10[k];
	}
};
bool operator<(const State &a,const State &b){
	return a.min_dist>b.min_dist;
}
int solve(){
	int ans=9999999;
	priority_queue<State> que;
	set<P> ac;
	if(digits[n-1]!=0){
		//個数が2の倍数
		for(int i=0;i<n;i++){
			if(digits[i]==0)continue;
			for(int j=i+1;j<n;j++){
				que.push(State(digits[j],digits[i],(1<<i)|(1<<j),n/2-1));
			}
		}
	}else{
		//個数が2の倍数ではない
		for(int i=0;i<n-1;i++){
			if(digits[i]==0)continue;
			que.push(State(digits[i],digits[n-1],(1<<(n-1)|(1<<i)),n/2-1));
		}
	}
	while(!que.empty()){
		State now=que.top();que.pop();
		if(ans<now.min_dist)break;
		ans=min(ans,now.max_dist);
		//使われていない数から適当に選ぶ
		if(now.used==(1<<n)-1)continue;//もう使える数が無い
		for(int i=0;i<n;i++){
			if((now.used>>i)&1)continue;
			for(int j=0;j<n;j++){
				if(i==j)continue;
				if((now.used>>j)&1)continue;
				//適当に二つの数を選ぶ
				int na=now.a*10+digits[i];
				int nb=now.b*10+digits[j];
				if(ac.find(P(na,nb))==ac.end()){
					ac.insert(P(na,nb));
					que.push(State(na,nb,now.used|(1<<i)|(1<<j),now.k-1));
				}
			}
		}
	}
	return ans;
}
int dfs(int x=-1,int y=-1,int used=0){
	if(used==(1<<n)-1&&x!=-1&&y!=-1){
		return abs(x-y);
	}

	int ans=99999999;
	for(int i=0;i<n;i++){
		if(((used>>i)&1)==0){
			if(x==-1)ans=min(ans,dfs(digits[i],y,used|(1<<i)));
			if(y==-1)ans=min(ans,dfs(x,digits[i],used|(1<<i)));
			if(x>0)ans=min(ans,dfs(x*10+digits[i],y,used|(1<<i)));
			if(y>0)ans=min(ans,dfs(x,y*10+digits[i],used|(1<<i)));
		}
	}
	return ans;
}
int main() {
	int tcase;
	string in;
	getline(cin,in);
	tcase=atoi(in.c_str());
	for(int T=0;T<tcase;T++){
		n=0;getline(cin,in);
		stringstream ss(in);
		while(ss>>digits[n])n++;
		if(n<5){
			cout<<dfs()<<endl;
		}else{
			if(n&1)digits[n++]=0;
			cout<<solve()<<endl;
		}
	}
	return 0;
}