2020 BIT冬训-C++图&&DFS&&BFS F - Smallest Difference POJ - 2718
标签：顺序 else continue c代码 其他 cstring 奇数 tchar scanf
Description - 题目描述
给定若干位十进制数，你可以通过选择一个非空子集并以某种顺序构建一个数。剩余元素可以用相同规则构建第二个数。除非构造的数恰好为0，否则不能以0打头。
举例来说，给定数字0，1，2，4，6与7，你可以写出10和2467。当然写法多样：210和764，204和176，等等。最后一对数差的绝对值为28，实际上没有其他对拥有更小的差。
Input - 输入
输入第一行的数表示随后测试用例的数量。
对于每组测试用例，有一行至少两个不超过10的十进制数字。（十进制数字为0，1，…，9）每行输入中均无重复的数字。数字为升序给出，相隔恰好一个空格。
Output - 输出
对于每组测试用例，输出一个以上述规则可获得的最小的差的绝对值在一行。
Sample Input - 输入样例
1
0 1 2 4 6 7
Sample Output - 输出样例
28
这题用贪心的做法。也可以用next_permutation。全排列出开头不为0的情况。然后计算。
这里我们用贪心的做法。
如果有奇数个数的数。
则两个数之间的位数相差1.则取除0以外最小值为较大数的首位，最大值为较小数的首位。然后令较大数的后几位按从前往后取，令较小数的后几位从后往前取。
如果有偶数个数的数。
则计算两个数之间的差。取差最小的且与0无关的那一对。若有多对差最小的数，则遍历一边寻找其中的最小值即可。
AC代码如下：
#include
#include
#includeusing namespace std;
int t,num[15],cnt,vis[15],cha[15],s1,s2,temp1,temp2,minn,ans;
char temp;
int main(){
scanf("%d",&t);
getchar();
while(t--){
memset(vis,0,sizeof(vis));
memset(cha,0,sizeof(cha));
temp1=0,temp2=0;
for(cnt=0;;cnt++){//cnt+1为数的个数（其中不用这样的但是积重难返了
temp=getchar();
if(‘0‘‘9‘)
num[cnt]=temp-‘0‘;
else if(temp==‘ ‘)
cnt--;
else if(temp==‘\n‘){
cnt--;
break;
}
}
if(cnt==1)
printf("%d\n",num[1]-num[0]);
else if(cnt&1){//由于cnt是从0开始。所以cnt为奇数的时候一共 有偶数个数
minn=25;
ans=0x3f3f3f3f;
for(int i=0;i){
if(!num[i])
continue;
cha[i]=num[i+1]-num[i];//下标为1~cnt-1
minn=minnminn:cha[i];
}
for(int i=0;i){
if(!num[i])
continue;
if(cha[i]==minn){
int tcnt=0;
memset(vis,0,sizeof(vis));
temp1=num[i+1],temp2=num[i];
vis[i]=1,vis[i+1]=1;
for(int i=0;;i++){
if(tcnt==cnt/2)
break;
if(!vis[i]){
temp1*=10;
temp1+=num[i];
vis[i]=1;
tcnt++;
}
}
tcnt=0;
for(int i=cnt;;i--){
if(tcnt==cnt/2)
break;
if(!vis[i]){
temp2*=10;
temp2+=num[i];
vis[i]=1;
tcnt++;
}
}
ans=anstemp2;
}
}
printf("%d\n",ans);
}else{//有奇数个数的数
for(int i=0;i)
if(num[i]){
s1=i;
break;
}
temp1=num[s1];
vis[s1]=1;
for(int i=0;i2;i++){
if(!vis[i]){
temp1*=10;
temp1+=num[i];
vis[i]=1;
}
}
for(int i=cnt;i>cnt/2;i--){
if(!vis[i]){
temp2*=10;
temp2+=num[i];
vis[i]=1;
}
}
printf("%d\n",temp1-temp2);
}
}
}
2020 BIT冬训-C++图&&DFS&&BFS F - Smallest Difference POJ - 2718
标签：顺序 else continue c代码 其他 cstring 奇数 tchar scanf
原文地址：https://www.cnblogs.com/mikku39/p/14460005.html
评论