18年后再次求解强盗分金问题

18年前，求解这个强盗分金问题花了我好久，磕磕碰碰总算能解出来，但是如今我想明白了，能解出来并不算什么，要得出标准答案才行，所以现在重新解决这个问题。代码如下：

size_t get_support_num(const std::vector<int>& result) {
    int ret = 0;
    for (auto i : result) {
        if (i >= 0)
            ret++;
    }
    return ret;
}

bool give_gold_num(std::vector<int>& this_result, const std::vector<int>& last_result) {
    int min_num = 0x7fffffff;
    int min_pos = -1;
    for (int i = 0; i < last_result.size(); i++) {
        if (this_result[i + 1] >= 0)
            continue;

        if (last_result[i] < min_num) {
            min_num = last_result[i];
            min_pos = i;
        }
    }

    if (min_pos == -1) {
        return false;
    }

    this_result[min_pos + 1] = min_num + 1;
    return true;
}

std::vector<int> robot_solution(int robot_num, int gold_num) {
    if (robot_num == 3) {
        std::vector<int> result;
        result.push_back(gold_num);
        result.push_back(0);
        result.push_back(0);
        return result;
    }

    std::vector<int> last_result = robot_solution(robot_num - 1, gold_num);
    std::vector<int> this_result(last_result.size() + 1, -1);
    while (get_support_num(this_result) + 1 <= this_result.size() / 2) {
        give_gold_num(this_result, last_result);
    }

    int gold_left = gold_num;
    for (int i = 1; i < this_result.size(); i++) {
        if (this_result[i] <= 0) {
            this_result[i] = 0;
        } else {
            gold_left -= this_result[i];
        }
    }

    this_result[0] = gold_left;
    return this_result;
}

嗨，一共只有五六十行代码就搞定了