1 条题解

  • 1
    @ 2026-9-4 16:51:45
    #include <vector>
    using namespace std;
    
    int n, c;
    vector<int> a;
    vector<long long> suffixSum; // 后缀和,用于剪枝
    vector<int> path;            // 记录选中的元素
    bool found = false;
    
    void dfs(int idx, int currentSum) {
        if (found) return;
    
        if (currentSum == c) {
            found = true;
            for (size_t i = 0; i < path.size(); i++) {
                if (i > 0) cout << " ";
                cout << path[i];
            }
            cout << endl;
            return;
        }
    
        if (idx >= n) return;
    
        // 剪枝:剩下的所有元素加起来都达不到目标
        if (currentSum + suffixSum[idx] < c) return;
    
        // 剪枝:当前和已经超过目标
        if (currentSum > c) return;
    
        // 先尝试包含当前元素(保证"最靠前"的解优先找到)
        if (currentSum + a[idx] <= c) {
            path.push_back(a[idx]);
            dfs(idx + 1, currentSum + a[idx]);
            path.pop_back();
            if (found) return;
        }
    
        // 再尝试不包含当前元素
        dfs(idx + 1, currentSum);
    }
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
    
        cin >> n >> c;
        a.resize(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
    
        // 预处理后缀和
        suffixSum.resize(n + 1, 0);
        for (int i = n - 1; i >= 0; i--) {
            suffixSum[i] = suffixSum[i + 1] + a[i];
        }
    
        // 总和都不够,直接无解
        if (suffixSum[0] < c) {
            cout << "No Solution!" << endl;
            return 0;
        }
    
        dfs(0, 0);
    
        if (!found) {
            cout << "No Solution!" << endl;
        }
    
        return 0;
    }
    
    
    
    • 1

    信息

    ID
    1302
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    8
    已通过
    3
    上传者