学校网站作用,甘肃网站建设哪家便宜,绿化公司网站建设,网站过期怎么找回来目录地址
前言
感谢黎某儿#xff08;划掉#xff09;教我这道题☆⌒(*#xff3e;-゜)v。 正题
给出两个n位数A,B。我们需要找到两个最近的靠近A的n位数#xff08;第一个比A大或与A相等#xff0c;第二个严格比A小#xff09;#xff0c;使得它们的十进制表示是B中…目录地址
前言
感谢黎某儿划掉教我这道题☆⌒(*-゜)v。 正题
给出两个n位数A,B。我们需要找到两个最近的靠近A的n位数第一个比A大或与A相等第二个严格比A小使得它们的十进制表示是B中所有数字的某个排列。 输入输出需要自取
Input
输入文件closest.in包含2行 第1行为一个正整数A。 第1行为一个正整数B。 A,B均为n位的正整数
Output
输出文件closest.out共有2行。 第一行最小的不比A小的n位数没有前导0包含B中的所有字符以某一顺序排列。如果这样的数不存在那么输出0。 第二行最大的比A小的n位数没有前导0包含B中的所有字符以某一顺序排列。如果这样的数不存在那么输出0。
Sample Input
输入样例1
3075 6604
输入样例2
3000203 4562454
Sample Output
输出样例1
4066 0
输出样例2
4244556 2655444 解题思路
B用桶存然后分两段输出一段是相等的和第一个不相等大的或小的第二段是将桶剩下的输出从大到小或从小到大然后用dfs更正。 代码
#includecstdio
#includeiostream
#includealgorithm
using namespace std;
int c[61],f[10],t[10],p[61];
char read;
int n,maxn,mark;
bool flag,flag2,ok;
void dfs(int i)//深搜
{if (in)//全部等于的情况{flagtrue;oktrue;for (int j1;jn;j) printf(%d,p[j]);return;}flag2false;for (int jc[i];j9;j){if (f[j]0){p[i]j;f[j]--;flag2true;if (jc[i])//找到一个了{flagtrue;break;}dfs(i1);//深搜if (ok) return;f[j];//回溯}}if (flag){for (int j1;ji;j) printf(%d,p[j]);//输出第一部分oktrue;return;}if (!flag2)//找不到了{return;}
}
void dfs2(int i)//相仿看上面↑
{if (in){oktrue;return;}flag2false;for (int jc[i];j0;j--){if (t[j]0 (i!1 || j!0)){p[i]j;t[j]--;flag2true;if (jc[i]){flagtrue;break;}dfs2(i1);if (ok) return;}}if (flag){for (int j1;ji;j) printf(%d,p[j]);oktrue;return;}if (!flag2){return;}
}
int main()
{while ((readgetchar())!\n){n;c[n]read-48;//输入}for (int i1;in;i) {cinread;t[read-48];f[read-48];}//输入flagfalse;okfalse;dfs(1);//搜if (!flag !flag2) printf(0);//找不到else for (int i0;i9;i)for (int j1;jf[i];j)printf(%d,i);//输出第二段printf(\n);flagfalse;dfs2(1);if (!flag !flag2) printf(0);else if(flag2 !flag){if (prev_permutation(p1,p1n))//如果连段可以全部相等就输出上一个排列for (int j1;jn;j) printf(%d,p[j]);}else for (int i9;i0;i--)for (int j1;jt[i];j)printf(%d,i);//输出第二段
}
