（贪心）最小差距

贪心）最小差距"/>

（贪心）最小差距

Problem A. 最小差距
时间限制 1000 ms
内存限制 128 MB
题目描述
　　给定一些不同的一位数字，你可以从这些数字中选择若干个，并将它们按一定顺序排列，组成一个整数，把剩下的数字按一定顺序排列，组成另一个整数。组成的整数不能以0开头（除非这个整数只有1位）。
　　例如，给定6个数字，0,1,2,4,6,7，你可以用它们组成一对数10和2467，当然，还可以组成其他的很多对数，比如210和764，204和176。这些对数中两个数差的绝对值最小的是204和176，为28。
　　给定N个不同的0~9之间的数字，请你求出用这些数字组成的每对数中，差的绝对值最小的一对（或多对）数的绝对值是多少？

输入数据
　　第一行包括一个数 T (T≤1000)， 为测试数据的组数。
　　每组数据包括两行，第一行为一个数 N (2≤N≤10)， 表示数字的个数。下面一行为 N 个不同的一位数字。
输出数据
T 行，每行一个数，表示第 i 个数据的答案。即最小的差的绝对值。
样例输入
2
6
0 1 2 4 6 7
4
1 6 3 4
样例输出
28
5
思路：（开始的思路不太对，只能让第一个例子正确，这说明解决问题的数学方式不对，选择的贪心策略决定了是否能取到最优解。）

下面是又过了一段时间，重新写的代码，思路都正确，但是，有一个细节没有注意到，就是数据中有0，并且只有两个数的情况下，l和r不应该++，会越界。（l是更小的那个数的最高位取值所在的数组下标，r是更大的）

#include<iostream>
#include<algorithm>
#define INF 1000000000
using namespace std;
int main(){int t;cin>>t;while(t!=0){int n;int a[15];cin>>n;for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n);
//		for(int i=0;i<n;i++){
//			cout<<a[i]<<" ";
//		}
//		cout<<endl;if(n%2==1){//不能零开头 if(a[0]==0){swap(a[0],a[1]);}int x=0,y=0;for(int i=0;i<n/2+1;i++){x=x*10+a[i];}for(int i=n-1;i>=n/2+1;i--){y=y*10+a[i];}//	cout<<x<<" "<<y<<endl;cout<<abs(x-y)<<endl;}else if(n%2==0){int x=0,y=0;int l=0,r=1;int res=INF;if(a[0]==0&&n>2){l++;r++;} while(r<n){x=a[l];y=a[r];//1.构建最高位更大的数,让他尽量小int i=0;int num=n/2-1;//后面可以取的个数 while(num!=0){if(i!=l&&i!=r){y=y*10+a[i]; num--;}i++; }//2.构建最高位更小的数，让他尽量大 i=n-1;num=n/2-1;while(num!=0){if(i!=l&&i!=r){x=x*10+a[i]; num--;}i--; }res=min(res,abs(y-x)); //	cout<<"x="<<x<<",y="<<y<<",res="<<res<<endl; l++;r++;}cout<<res<<endl;}t--;} }