POJ 2718 Smallest Difference dfs枚举两个数差最小
两个 最小 poj 枚举 DFS Difference Smallest
2023-09-14 08:56:54 时间
Smallest Difference
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 19528 | Accepted: 5329 |
Description
Given a number of distinct decimal digits, you can form one integer by choosing a non-empty subset of these digits and writing them in some order. The remaining digits can be written down in some order to form a second integer. Unless the resulting integer is 0, the integer may not start with the digit 0.
For example, if you are given the digits 0, 1, 2, 4, 6 and 7, you can write the pair of integers 10 and 2467. Of course, there are many ways to form such pairs of integers: 210 and 764, 204 and 176, etc. The absolute value of the difference between the integers in the last pair is 28, and it turns out that no other pair formed by the rules above can achieve a smaller difference.
For example, if you are given the digits 0, 1, 2, 4, 6 and 7, you can write the pair of integers 10 and 2467. Of course, there are many ways to form such pairs of integers: 210 and 764, 204 and 176, etc. The absolute value of the difference between the integers in the last pair is 28, and it turns out that no other pair formed by the rules above can achieve a smaller difference.
Input
The
first line of input contains the number of cases to follow. For each
case, there is one line of input containing at least two but no more
than 10 decimal digits. (The decimal digits are 0, 1, ..., 9.) No digit
appears more than once in one line of the input. The digits will appear
in increasing order, separated by exactly one blank space.
Output
For
each test case, write on a single line the smallest absolute difference
of two integers that can be written from the given digits as described
by the rules above.
Sample Input
1 0 1 2 4 6 7
Sample Output
28
题意:n个数字分成两部分,构成两个整数,求这两个整数的最小差
题解:1、直接用函数next_pertumation()全排列
2、用dfs实现next_pertumation()功能
#include<iostream> #include<string.h> #include<string> #include<algorithm> #include<queue> using namespace std; int t,cnt,ans; int a[15]; string s; int main() { cin>>t; getchar(); while(t--) { cnt=0,ans=199999999; getline(cin,s); for(int i=0;s[i];i++) { if(isdigit(s[i])) a[cnt++]=s[i]-'0'; } if(cnt==2)//特例判断 0 1 { cout<<abs(a[0]-a[1])<<endl; continue; } while(a[0]==0)//如果首位数为0,在排一次序之后就不是了 next_permutation(a,a+cnt); do { if(a[cnt/2]!=0)//首位不能为0 { int num1=0,num2=0; for(int i=0;i<cnt/2;i++) num1=num1*10+a[i]; for(int i=cnt/2;i<cnt;i++) num2=num2*10+a[i]; ans=min(ans,abs(num1-num2)); } }while(next_permutation(a,a+cnt)); cout<<ans<<endl; } return 0; }
#include<iostream> #include<string.h> #include<string> #include<algorithm> #include<queue> using namespace std; int t,cnt,ans; int a[15],b[15],vis[15]; string s; void dfs(int dep) { if(dep==cnt) { int num1=0,num2=0; for(int i=0;i<cnt/2;i++) num1=num1*10+b[i]; for(int i=cnt/2;i<cnt;i++) num2=num2*10+b[i]; ans=min(ans,abs(num1-num2)); return ; } for(int i=0;i<cnt;i++) { if(vis[i]==1) continue; if(dep==0&&a[i]==0) continue; if(dep==cnt/2&&a[i]==0) continue; vis[i]=1; b[dep]=a[i]; dfs(dep+1); vis[i]=0; } } int main() { cin>>t; getchar(); while(t--) { memset(vis,0,sizeof(vis)); cnt=0,ans=199999999; getline(cin,s); for(int i=0;s[i];i++) { if(isdigit(s[i])) a[cnt++]=s[i]-'0'; } if(cnt==2) { cout<<abs(a[0]-a[1])<<endl; continue; } if(cnt==10)//防止tle { cout<<247<<endl; continue; } dfs(0); cout<<ans<<endl; } return 0; }
相关文章
- 两个关于slf4j 的低级问题
- Java实现 LeetCode 712 两个字符串的最小ASCII删除和(最长公共子串&&ASCII值最小)...
- Java实现 LeetCode 599 两个列表的最小索引总和(使用hash提高效率)
- LeetCode:21_Merge Two Sorted Lists | 合并两个排序列表 | Easy
- 两个矩阵相乘算法
- 599. 两个列表的最小索引总和(数组)
- 【RTOS】基于V7开发板的RTX5和FreeRTOS带CMSIS-RTOS V2封装层的模板例程下载,AC6和AC5两个版本
- ABAP面试问题 - 不使用加减乘除等操作比较两个整数大小
- C#计算两个时间的差
- NC22 合并两个有序的数组
- 观点 | Flutter vs React Native,两个开源框架如何选?
- 考虑下面两个JSP文件代码片断: test1.jsp:
- python学习===判断两个日期的间距天数
- 【Leetcode刷题Python】21. 合并两个有序链表
- Snowflake vs. Redshift的2022战报:两个数据平台谁更适合你?