POJ 2718
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int numbers[10];
int length;
int n;
int permutation(int num[10]){
int i; int oneco=0;
for(i=0;i<length;i++){
if(num[i]){oneco++;}
}
int length2 = length-oneco;
if((oneco==length)||(oneco==0)){return 1000000000;}
if(abs(length2-oneco)>=2){return 1000000000;}
vector<int> one;
vector<int> two;
for(int i=0;i<length;i++){
if(num[i]){one.push_back(numbers[i]);}
else{two.push_back(numbers[i]);}
}
int len1 = one.size();
int len2 = two.size();
//cout << len1 << len2 << endl;
// int num1[10];int num2[10];
vector<int> num1;
vector<int> num2;
//cout << one[1] << one[2] << endl;
int count1=0;int count2 = 0;
sort(one.begin(),one.end());
sort(two.begin(),two.end());
do{
int num=0;
for(int i=1;i<len1;i++){
int onei = one[i];
for(int i2=0;i2<i;i2++){
onei = onei*10;
}
num = num + onei;
}//cout << num << endl;
if(one[0]==0){num = num;}
else {num = num + one[0];}
num1.push_back(num);
//cout << num << endl;
count1++;
}while(next_permutation(one.begin(),one.end()));
do{
int num = 0;
for(int i=1;i<len2;i++){
int twoi = two[i];
for(int i2 =0;i2<i;i2++){
twoi = twoi*10;
}
num = num + twoi;
// cout << num << endl;
}//cout << "here" << num << endl;
if(two[0]==0){num = num;}
else {//cout << num ;
num = num + two[0];
//cout << " " << num << endl;
}
num2.push_back(num);
//cout << "here" << num << endl;
count2++;
}while(next_permutation(two.begin(),two.end()));
int ans = 1000000000;
//cout << len2;
int dummy1 = 1;
for(int x=1;x<len1;x++){
dummy1 = dummy1*10;
}//cout << dummy1;
int dummy2 = 1;
for(int x=1;x<len2;x++){//cout << dummy2<< endl;
dummy2 = (dummy2)*10;
//cout << dummy2<< endl;
}//cout << dummy2;
for(int i=0;i<count1;i++){//cout << num1[i] << dummy1 << endl;
if((num1[i]%dummy1)==num1[i]){if(num1[i]!=0){continue;}}
for(int i2=0;i2<count2;i2++){
if((num2[i2]%dummy2)==num2[i2]){if(num1[i]!=0){continue;}}
ans = min(ans,abs(num1[i]-num2[i2]));
}
}
return ans;
}
//int permutation(int i[10]){return 1;}
int dfs(int i,int num[10]){
if(i==length) return permutation(num);
num[i]=0;
int ans1 = dfs(i+1,num);
num[i]=1;
int ans2 = dfs(i+1,num);
return min(ans1,ans2);
}
int main(){
cin >> n;
getchar();
for(int i=0;i<n;i++){
/*for(length=0;length<10;length++){
cin >> numbers[length];
char c = getchar();
if(c=='\n'){break;}
}*/
string str;
while(1){
char c = getchar();
if(c=='\n'){break;}
str += c;}
length = 0;
for(int i2=0;i2<str.length();i2=i2+2){
numbers[length] = (int)str[i2]-'0';
length++;
}
// cout << length;
int dummy[10] = {0,0,0,0,0,0,0,0,0,0};
cout << dfs(1,dummy) << endl;
}
}
上記のどこが間違っているか教えてください。POJの2718です。書いてあるテストは通りました。
お礼
ありがとうございます、解を求めることができました！！