Backward Digit Sums G/S

链接

这题需要结合两个知识,一个是输出全排列,另一个是求出杨辉三角的某一行

二者并不难,唯一的难点是超时问题,题目最大是12

而12!非常大,因此我们需要采取一些策略减少遍历次数,也就是剪枝

我们看题目的输入样例 4 16 也就是说我们需要找到合适的排列,使

1 2 3 4

1 3 3 1(杨辉三角)

两个数组对应元素相乘等于16

当我们确定第一个数字为1的时候,当前总和为1x1=1,我们可以思考,如果当前和加上剩下的最大可能和都小于16或者当前和加上最小可能和大于16的时候,就证明1放在第一个数是不正确的

最大可能和直观来讲就是大数乘大数,也就是1+2x1+3x3+4x3=24<16

而最小可能和则相反,就是1+2x3+3x3+4x1=20>16

我们发现,当1放在第一位时,最小可能和都大于16,那么其他的可能和就都大于16了,所以这种情况直接忽略不管

那么,最大可能和真的是那么求的吗,是的

根据排序不等式顺序和>乱序和>倒序和,可知,我们的只管感觉没错

回到题目,1不能放在第一位,那么2可以吗?不行,最小可能和为18,依旧超过

依次类推,我们可以得到最终答案为3 1 4 2(题目要求字典序最小的结果输出,所以是这个答案)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void dfs(int pos, int currentSum, int n, int m,
    vector<int>& weights, vector<int>& ans,
    vector<bool>& used, bool& found) {
    if (found) return;
    // 剪枝：如果当前和已经超过目标值
    if (currentSum > m) return;
    int max_value = currentSum, min_value = currentSum;
    vector<int>residual;
    vector<int>res;
    for (int i = 0;i < n;i++) {
        if (!used[i]) {
            residual.push_back(i + 1);
        }
    }
    for (int i = pos;i < n;i++) {
        res.push_back(weights[i]);
    }
    sort(residual.begin(), residual.end());
    sort(res.begin(), res.end());
    for (int i = 0;i < res.size();i++) {
        max_value += res[i] * residual[i];
        min_value += res[i] * residual[res.size() - i - 1];
    }
    if (max_value < m) return;
    if (min_value > m) return;
    if (pos == n) {
        if (currentSum == m) { 
            found = true;
            for (int i = 0; i < n; i++) {
                cout << ans[i];
                if (i < n - 1) cout << " ";
            }
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = true;
            ans[pos] = i + 1;
            dfs(pos + 1, currentSum + (i + 1) * weights[pos],
                n, m, weights, ans, used, found);
            if (found) return;
            used[i] = false;
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> weights(n);
    weights[0] = 1;
    for (int i = 1; i < n; i++) {
        weights[i] = weights[i - 1] * (n - i) / i;
    }

    vector<int> ans(n);
    vector<bool> used(n, false);
    bool found = false;

    dfs(0, 0, n, m, weights, ans, used, found);

    return 0;
}

时间复杂度:好吧,我也算不来

空间复杂度:O(n)