8:最少的木棍数量 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65535kB 描述 给定不同长度的木棍sticks和一个目标长度length。请你计算可以拼接成该长度所需的最少的木棍个数。如果没有任何一种组合能组成目标长度，输出 -1。 每种长度的木棍的数量是无限的。 输入 第一行只有一个数字，表示木棍长度种数n 第二行包含n个以空格分隔的数字，表示不同长度的木棍sticks 第三行只有一个数字，表示目标长度length 输出 可以拼成该长度所需的最少的木棍个数。（如果没有这样的组合，输出-1）（使用c++）

以下是使用C++实现的代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, length;
    cin >> n;
    vector<int> sticks(n);
    for (int i = 0; i < n; i++) {
        cin >> sticks[i];
    }
    cin >> length;

    sort(sticks.begin(), sticks.end(), greater<int>());

    int count = 0, total = 0, index = 0;
    while (total < length && index < n) {
        if (sticks[index] <= length - total) {
            count += (length - total) / sticks[index];
            total += (length - total) % sticks[index];
        }
        index++;
    }

    if (total == length) {
        cout << count << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}

该程序使用vector来存储木棍长度，并使用STL中的sort函数按从大到小排序。然后使用贪心算法计算最少需要的木棍数量。

具体实现过程与Python实现类似，使用count变量记录已经使用的木棍数量，total变量记录已经拼接好的长度，index变量从后往前遍历木棍长度。每次循环时，如果当前木棍可以用于拼接目标长度，就将计数器加上目标长度和当前木棍长度的商，然后将已经拼接好的长度加上目标长度和当前木棍长度的余数。如果已经拼接好的长度等于目标长度，就直接输出计数器的值。如果遍历完所有的木棍后仍然无法拼接出目标长度，就输出-1。