Balkan2008 closest 题解

Edited on | In | Comments:

Problem

问题描述：

有两个没有前导$0$的$n$位十进制数$A$和$B$。我们需要找到两个最接近$A$的$n$位数(第1个大于等于$A$，第二小于$A$)，包含B的所有数字。

例如，如果$A=3022$，$B=1232$，采用$B$的数字，我们可以得到以下$4$位数:$1223$，$1232$，$1322$，$2123$，$2132$，$2213$，$2231$，$2312$，$2321$，$3122$，$3212$和$3221$。

最小的大于等于$A$是$3122$，最大小于$A$的是$2321$。

如果$A=1232$，而$B=3022$，可能的$4$位数是$2023$，$2032$，$2203$，$2230$，$2302$，$2320$，$3022$，$3202$和$3220$。

最小的大于等于$A$是$3122$，最大小于$A$的是$2023$。不存在小于$4$的数。

编写程序，对于给定的$A$和$B$，找出最接近$A$的包含$B$的所有数字的数，或者确定其中一个是不存在的。

输入格式：

输入两行，都是没有前导$0$的$n(1≤n≤60)$位正整数，第一行是$A$，第二行是$B$。

输出格式：

输出两行，每行一个十进制数。

第1行是最小的大于等于$A$的没有前导$0$的，包含$B$所有数字的$n$位十进制数。如果这样的数不存在，则输出$0$。

第2行是最大的小于$A$的没有前导$0$的，包含$B$所有数字的$n$位十进制数。如果这样的数不存在，则输出$0$。

样例输入输出：

1
2
3
Input #1
3075
6604
1
2
3
Output #1
4066
0
1
2
3
Input #2
3000203
4562454
1
2
3
Output #2
4244556
2655444

Solution

本题难度不高。

很容易想到，既然越接近越好，那么就一位一位匹配，能匹配上就用，如果发现完成不了回溯就行了。

这题主要是注意下细节，调试可能比较烦，算法很简单，耐心做就OK了。

具体算法详见代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;

string a, b;
int len;
int cntl[10], cntr[10];
bool found;
int last;
int ans[65];

bool dfs1(int s, int depth)
{
    if (depth == len) return false;
    int start = 0;
    bool fail = true;
    int now = a[depth] - '0';
    if (s) start = now;
    for (int i = start; i <= 9; i++) if (cntl[i])
    {
        cntl[i]--, ans[depth] = i;
        if(i == start && s) s = 1;
        else s = 0;
        fail = dfs1(s, depth + 1);
        if (fail) cntl[i]++;
        else {fail = false; break;}
    }
    return fail;
}

bool dfs2(int s, int depth)
{
    if (depth == len) return false;
    int start = 9;
    bool fail = true;
    int now = a[depth] - '0';
    if (s)
    {
        start = now;
        if (depth == len - 1) start--;
    }
    for (int i = start; i >= 0 + (!depth); i--) if (cntr[i])
    {
        cntr[i]--, ans[depth] = i;
        if(i == start && s) s = 1;
        else s = 0;
        fail = dfs2(s, depth + 1);
        if (fail) cntr[i]++;
        else {fail = false; break;}
    }
    return fail;
}

int main()
{
    cin >> a >> b;
    len = a.length();
    for (int i = 0; i < len; i++) cntl[b[i] - '0']++, cntr[b[i] - '0']++;
    if (dfs1(1, 0)) cout << "0";
    else for (int i = 0; i < len; i++) cout << ans[i];
    cout << endl;
    if (dfs2(1, 0)) cout << "0";
    else for (int i = 0; i < len; i++) cout << ans[i];
    cout << endl;
    return 0;
}

Data

评测请至洛谷SP3889。