2020 阿里笔试：最少出牌次数

发表于 | 分类于

记一次没剪枝的爆搜。

题目来源

阿里巴巴2020实习生招聘在线笔试（3月20日场）

题目描述

有一叠扑克牌，每张牌介于1和10之间，有四种出牌方法：

  1. 单牌
  2. 对子
  3. 顺子：如12345
  4. 连对：如112233

给10个数，表示1-10每种牌有几张，问最少要多少次能出完

输入样例

1 1 1 2 2 2 2 2 1 1

输出样例

3

样例说明：出三个顺子：A2345，45678，678910

当时的思路

1
2
3
4
5
6
当前打法的最少次数 = min {
        打出单张后的最少次数 + 1，
        打出一个对子后的最少次数 + 1，
        打出一个顺子后的最少次数 + 1，
        打出一个连对后的最少次数 + 1
}

这思路甚至让我有种是不是可以用动规的错觉。

错误示范

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <vector>
using namespace std;

const int MAX_COUNT = 40;

int recursivePoke(vector<int> &poke, int totalPoke) {
    for (int num : poke) {
        cout << num << ' ' << endl;
    }
    cout << endl;
    if (totalPoke <= 0) {
        return 0;
    }
    if (totalPoke == 1) {
        return 1;
    }

    int ans = MAX_COUNT;
    int recursiveResult;
    bool flag;

    // 单牌
    for (size_t i = 0; i < 10; ++i) {
        if (poke[i] > 0) {
            int tmp = poke[i];
            poke[i] = 0;
            recursiveResult = recursivePoke(poke, totalPoke - tmp);
            if (recursiveResult + tmp < ans) {
                ans = recursiveResult + tmp;
            }
            poke[i] += tmp;
        }
    }

    // 对子
    for (size_t i = 0; i < 10; ++i) {
        if (poke[i] > 1) {
            poke[i] -= 2;
            recursiveResult = recursivePoke(poke, totalPoke - 2);
            if (recursiveResult + 1 < ans) {
                ans = recursiveResult + 1;
            }
            poke[i] += 2;
        }
    }

    // 顺子
    if (totalPoke >= 5) {
        for (size_t i = 0; i < 10; ++i) {
            flag = true;    // 有顺子
            for (size_t j = i; j < i + 5; ++i) {
                if ((j < 10 && poke[j] == 0) || j >= 10) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                for (size_t j = i; j < i + 5; ++i) {
                    --poke[j];
                }
                recursiveResult = recursivePoke(poke, totalPoke - 5);
                if (recursiveResult + 1 < ans) {
                    ans = recursiveResult + 1;
                }
                for (size_t j = i; j < i + 5; ++i) {
                    ++poke[j];
                }
            }
        }
    }

    // 连对
    if (totalPoke >= 6) {
        for (size_t i = 0; i < 10; ++i) {
            flag = true;    // 有连对
            for (size_t j = i; j < i + 3; ++j) {
                if ((j < 10 && poke[j] < 2) || j >= 10) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                for (size_t j = i; j < i + 3; ++j) {
                    poke[j] -= 2;
                }
                recursiveResult = recursivePoke(poke, totalPoke - 6);
                if (recursiveResult + 1 < ans) {
                    ans = recursiveResult + 1;
                }
                for (size_t j = i; j < i + 5; ++i) {
                    poke[j] += 2;
                }
            }
        }
    }

    return ans;
}

int main()
{
    vector<int> poke(10);
    int totalPoke = 0;
    for (size_t i = 0; i < 10; ++i) {
        cin >> poke[i];
        totalPoke += poke[i];
    }

    cout << recursivePoke(poke, totalPoke);

    return 0;
}

当我写完美滋滋地提交之后，拿到了一个 TLE。然后开 IDE 调了挺久，一下子也想不出来怎么剪枝，发现时间不太够了就想着能不能去水一下第二题，结果直接全都白给，惨遭零封了，其实是以为这次要凉凉了，愤而刷了一整天的 LeetCode 搜索题。晚上又接到阿里的面试电话，聊了差不多四十分钟，感觉好像又有点希望了，才又把这段代码翻出来复盘。不知道是没睡醒还是本来就菜，问题一大堆：

  1. 把 ++j 写成了 ++i，包括第52、59、66、91行四处
  2. 第91行还有一个，应该是 i + 3 的写成了 i + 5，导致牌数不断增加死循环跳不出来了

把这些小问题整完之后，发现代码跑的还是很慢，看了下别人的思路，感觉好像都一样呀，复杂度是 $4^{10}$，一百多万嘛，开了个全局变量，跑半天终于超过了这个迭代次数后发现还是没停下来，说明搜索空间还是有问题的（这不是很明显吗？）。

看了一下这道题下的讨论后，对单牌和顺子的情况增加了一个判断进行剪枝，即搜索前加一个 ans == MAX_COUNT，但这个判断在不能出顺子或连对的情况下还是起不到明显的剪枝效果。

而 NOIP 2015 提高组 Day1 第三题斗地主和这道题神似，看了解题思路后才发现，可以加入一点贪心的思想，把顺子和连对这些情况放到前面，然后单牌和对子就不用进行迭代了，直接全丢出去就好了。单牌和对子的迭代正是导致搜索空间爆炸的根本原因啊！！！真实菜到抠脚，研一了还不如高中生…

修改后的代码

应该没问题了…

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <vector>
using namespace std;

const int MAX_COUNT = 40;

int recursivePoke(vector<int> &poke, int totalPoke) {
    if (totalPoke <= 0) {
        return 0;
    }
    if (totalPoke == 1) {
        return 1;
    }

    int ans = MAX_COUNT;
    int recursiveResult;
    bool flag;

    // 顺子
    if (totalPoke >= 5) {
        for (size_t i = 0; i < 10; ++i) {
            flag = true;    // 有顺子
            for (size_t j = i; j < i + 5; ++j) {
                if ((j < 10 && poke[j] == 0) || j >= 10) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                for (size_t j = i; j < i + 5; ++j) {
                    --poke[j];
                }
                recursiveResult = recursivePoke(poke, totalPoke - 5);
                if (recursiveResult + 1 < ans) {
                    ans = recursiveResult + 1;
                }
                for (size_t j = i; j < i + 5; ++j) {
                    ++poke[j];
                }
            }
        }
    }

    // 连对
    if (totalPoke >= 6) {
        for (size_t i = 0; i < 10; ++i) {
            flag = true;    // 有连对
            for (size_t j = i; j < i + 3; ++j) {
                if ((j < 10 && poke[j] < 2) || j >= 10) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                for (size_t j = i; j < i + 3; ++j) {
                    poke[j] -= 2;
                }
                recursiveResult = recursivePoke(poke, totalPoke - 6);
                if (recursiveResult + 1 < ans) {
                    ans = recursiveResult + 1;
                }
                for (size_t j = i; j < i + 3; ++j) {
                    poke[j] += 2;
                }
            }
        }
    }

    // 对子
    if (ans == MAX_COUNT) {
        recursiveResult = 0;
        for (int &num : poke) {
            recursiveResult += (num / 2);
            num %= 2;
            recursiveResult += num;
        }
        ans = recursiveResult;
    }

    // 单牌
    if (ans == MAX_COUNT) {
        ans = 0;
        for (int num : poke) {
            ans += num;
        }
    }

    return ans;
}

int main()
{
    vector<int> poke(10);
    int totalPoke = 0;
    for (int &num : poke) {
        cin >> num;
        totalPoke += num;
    }
    cout << recursivePoke(poke, totalPoke);
    return 0;
}

相关链接