【题目描述】 给定一些不同的一位数字，你可以从这些数字中选择若干个，并将它们按一定顺序排列，组成一个整数，把剩下的数字按一定顺序排列，组成另一个整数。组成的整数不能以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 【分析】 首先想到的算法是暴力穷举，但是时间复杂度无法承受。 于是我们考虑贪心策略。 首先把这N个数降序排列，这一点应该不用解释了。 接下来分类讨论： N为奇数/N为偶数/N=2 对于第一种情况，不难想到这样的贪心策略：将最小的非0数字作为x的最高位，然后依次从左往右取k位加入x，从右往左取k位作为y，x-y的绝对值即为答案。 对于第二种情况，稍微复杂些：枚举非零数字a[i]作为x的最高位，a[i+1]作为y的最高位，从右往左取k-1位加入x，从左往右取k-1位加入y，打擂台更新答案。 对于第三种情况，特判输出。 C++：
#include<bits/stdc++.h>using namespace std;int a[15];int n;int abs(int x){ return (x<0?-x:x); }int work1(){ if (a[1]==0) swap(a[1],a[2]); int s1=0,s2=0; for (int i=1;i<=n/2+1;i++) s1=s1*10+a[i]; for (int i=n;i>=n/2+2;i--) s2=s2*10+a[i]; return abs(s1-s2);}int work2(){ int book[15]; int s1,s2; int ans=(1<<31)-1; for (int i=2;i<=n;i++) if (a[i-1]){ s1=a[i],s2=a[i-1]; memset(book,0,sizeof(book)); book[i]=book[i-1]=1; int l=1,r=n; for (int j=1;j<=(n-2)/2;j++){ while (book[l]) l++; while (book[r]) r--; book[l]=book[r]=1; s1=s1*10+a[l];s2=s2*10+a[r]; } ans=min(ans,abs(s1-s2)); } return ans;}int main(){ int t; cin>>t; while (t--){ scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); if (n==2) { PRintf("%d/n",a[2]-a[1]);continue; } if (n%2==1) printf("%d/n",work1()); else printf("%d/n",work2()); }}Pascal：
var t,n,i,j:longint; a:array[0..10] of longint;procedure qsort(aa,bb:longint);var i,j,x:longint;begin i:=aa;j:=bb; x:=a[(i+j) div 2]; repeat while a[i]<x do inc(i); while a[j]>x do dec(j); if i<=j then begin a[0]:=a[i];a[i]:=a[j];a[j]:=a[0]; inc(i);dec(j); end; until i>j; if i<bb then qsort(i,bb); if j>aa then qsort(aa,j);end;procedure work1;var s1,s2,tip:string; i,a1,a2:longint;begin s1:='';s2:=''; if a[1]=0 then begin a[0]:=a[1]; a[1]:=a[2]; a[2]:=a[0]; end; for i:=1 to n div 2+1 do begin str(a[i],tip); s1:=s1+tip; end; for i:=n downto n div 2+2 do begin str(a[i],tip); s2:=s2+tip; end; val(s1,a1); val(s2,a2); writeln(abs(a1-a2));end;procedure work2;var ans,j,i,a1,a2,min,max:longint; tip,s1,s2:string; use:array[1..10] of boolean;begin ans:=maxlongint; for i:=2 to n do if a[i-1]<>0 then begin s1:='';s2:=''; str(a[i],tip); s1:=s1+tip; str(a[i-1],tip); s2:=s2+tip; fillchar(use,sizeof(use),false); use[i-1]:=true;use[i]:=true; min:=1;max:=n; for j:=1 to (n-2) div 2 do begin while use[min] do inc(min); while use[max] do dec(max); str(a[min],tip); use[min]:=true; s1:=s1+tip; str(a[max],tip); use[max]:=true; s2:=s2+tip; end; val(s1,a1); val(s2,a2); if abs(a1-a2)<ans then ans:=abs(a1-a2); end; writeln(ans);end;begin readln(t); for i:=1 to t do begin readln(n); for j:=1 to n do read(a[j]); qsort(1,n); if n=2 then writeln(abs(a[1]-a[2])) else begin if n mod 2=1 then work1; if n mod 2=0 then work2; end; end;end.新闻热点
疑难解答
