2020 BIT冬训-C++图&&DFS&&BFS F - Smallest Difference POJ - 2718
2021-06-10 09:04
阅读：550
标签：顺序 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）每行输入中均无重复的数字。数字为升序给出，相隔恰好一个空格。
对于每组测试用例，有一行至少两个不超过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 #include using 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=minn minn: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=ans temp2; } } 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
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：2020 BIT冬训-C++图&&DFS&&BFS F - Smallest Difference POJ - 2718
文章链接：http://soscw.com/essay/93080.html
文章标题：2020 BIT冬训-C++图&&DFS&&BFS F - Smallest Difference POJ - 2718
文章链接：http://soscw.com/essay/93080.html
评论
亲，登录后才可以留言！