POJ 2718 Smallest Difference(暴力,全排列，next_permutation)

本文主要是介绍POJ 2718 Smallest Difference(暴力,全排列，next_permutation)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://poj.org/problem?id=2718

题意：给出2-10个数（个位数0-9），用这几个数组成两个数（除0之外，首位不能为0），求这两个数的最小值。

题解：两个数差值最小首先保证位数差值最小，所以对这几个数从中间分开，组成两个数，求出差值。用到STL中的next_permutation()函数。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
const int INF=0x3f3f3f3f;
int num[12];
char s[30];
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int t;scanf("%d",&t);getchar();while(t--){gets(s);int t=0;for(int i=0;s[i];i++){if(isdigit(s[i])){num[t++]=s[i]-'0';}}sort(num,num+t);int ans=INF;int a,b;do{/*for(int i=0;i<t;i++){printf("%d",num[i]);}printf("\n");*/if(num[0]==0){a=0;b=0;for(int i=1;i<t;i++)b=b*10+num[i];ans=min(ans,abs(a-b));}else {if(num[0]==0&&t/2>=1) continue;if(num[t/2]==0&&t-t/2>=1) continue;a=0;b=0;for(int i=0;i<t/2;i++){a=a*10+num[i];}for(int i=t/2;i<t;i++){b=b*10+num[i];}ans=min(ans,abs(a-b));}}while(next_permutation(num,num+t));printf("%d\n",ans);}return 0;
}

这篇关于POJ 2718 Smallest Difference(暴力,全排列，next_permutation)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---