目錄地址

前言

感謝黎某兒（劃掉）教我這道題☆⌒(*＾-゜)v。

---

正題

給出兩個n位數(shù)A,B。我們需要找到兩個最近的靠近A的n位數(shù)（第一個比A大或與A相等，第二個嚴格比A小），使得它們的十進制表示是B中所有數(shù)字的某個排列。

---

輸入輸出（需要自取）

Input

輸入文件closest.in包含2行：
第1行為一個正整數(shù)A。
第1行為一個正整數(shù)B。
（A,B均為n位的正整數(shù)）

Output

輸出文件closest.out共有2行。
第一行：最小的不比A小的n位數(shù)，沒有前導0，包含B中的所有字符，以某一順序排列。如果這樣的數(shù)不存在，那么輸出0。
第二行：最大的比A小的n位數(shù)，沒有前導0，包含B中的所有字符，以某一順序排列。如果這樣的數(shù)不存在，那么輸出0。

Sample Input

輸入樣例1

3075
6604

輸入樣例2

3000203
4562454

Sample Output

輸出樣例1

4066
0

輸出樣例2

4244556
2655444

---

解題思路

B用桶存，然后分兩段輸出，一段是相等的和第一個不相等（大的或小的），第二段是將桶剩下的輸出（從大到小或從小到大），然后用dfs更正。

---

代碼

#include<cstdio> #include<iostream> #include<algorithm> 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 (i>n)//全部等于的情況{flag=true;ok=true;for (int j=1;j<=n;j++) printf("%d",p[j]);return;}flag2=false;for (int j=c[i];j<=9;j++){if (f[j]>0){p[i]=j;f[j]--;flag2=true;if (j>c[i])//找到一個了{flag=true;break;}dfs(i+1);//深搜if (ok) return;f[j]++;//回溯}}if (flag){for (int j=1;j<=i;j++) printf("%d",p[j]);//輸出第一部分ok=true;return;}if (!flag2)//找不到了{return;} } void dfs2(int i)//相仿，看上面↑ {if (i>n){ok=true;return;}flag2=false;for (int j=c[i];j>=0;j--){if (t[j]>0 && (i!=1 || j!=0)){p[i]=j;t[j]--;flag2=true;if (j<c[i]){flag=true;break;}dfs2(i+1);if (ok) return;}}if (flag){for (int j=1;j<=i;j++) printf("%d",p[j]);ok=true;return;}if (!flag2){return;} } int main() {while ((read=getchar())!='\n'){n++;c[n]=read-48;//輸入}for (int i=1;i<=n;i++) {cin>>read;t[read-48]++;f[read-48]++;}//輸入flag=false;ok=false;dfs(1);//搜if (!flag && !flag2) printf("0");//找不到else for (int i=0;i<=9;i++)for (int j=1;j<=f[i];j++)printf("%d",i);//輸出第二段printf("\n");flag=false;dfs2(1);if (!flag && !flag2) printf("0");else if(flag2 && !flag){if (prev_permutation(p+1,p+1+n))//如果連段可以全部相等就輸出上一個排列for (int j=1;j<=n;j++) printf("%d",p[j]);}else for (int i=9;i>=0;i--)for (int j=1;j<=t[i];j++)printf("%d",i);//輸出第二段 }

總結(jié)

以上是生活随笔為你收集整理的【2018.3.10】模拟赛之一-ssl2574Closest【深搜】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。