A25067. 小白兔拔萝卜
填空题
困难
知识点
题目描述
小白兔拔萝卜
题目描述
小白兔拔萝卜，但是它的力量有限，太大的萝卜它拔不动。于是它叫来了一群小伙伴……
本题就请你根据小白兔们的力量和拔出这个萝卜需要的力量，告诉小白兔，它最少需要哪些伙伴能拔出这只大萝卜。
输入描述
输入在第一行里给出两个不超过 1000 的正整数 n 和 T，分别是小白兔的数量和拔出这个萝卜需要的力量。
随后一行给出 n 个不超过 100 的正整数，其中第 i 个数对应编号为 i 的小白兔的力量（i=1, … , n）。
输出描述
如果兔子们有可能拔成功，则首先在第一行输出最少需要多少只兔子才能拔出这只萝卜，然后第二行从小到大输出参与拔萝卜的兔子们的编号。编号间以 1 个空格分隔，行首尾不得有多余空格。
如果所有兔子合力都不能拔出萝卜，则首先在第一行输出 0，随后在第二行中输出：Suan4 le ba, hai2 cha4 X. 其中 X 是小白兔们缺少的力量值。
注意：力量等于 T 是可以拔出萝卜的。 解可能不是唯一的，你只要随便输出一组就可以。
样例输入1
10 100
3 25 4 91 13 81 64 38 49 51样例输出1
2
2 4样例输入2
5 50
3 2 8 5 10样例输出2
0
Suan4 le ba, hai2 cha4 22.参考答案
//答案来源于AI
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
const int INF = 10000;
int main() {
int n, T;
cin >> n >> T;
vector<int> powers(n);
long long total = 0;
for (int i = 0; i < n; i++) {
cin >> powers[i];
total += powers[i];
}
// 处理总力量不足的情况
if (total < T) {
cout << "0" << endl;
cout << "Suan4 le ba, hai2 cha4 " << T - total << "." << endl;
return 0;
}
// 动态规划数组，dp[j]表示达到力量j所需的最少兔子数
vector<int> dp(T + 1, INF);
// 记录状态转移路径
vector<int> prevState(T + 1, -1);
vector<int> lastId(T + 1, -1);
// 初始状态：0力量需要0只兔子
dp[0] = 0;
// 动态规划过程
for (int i = 0; i < n; i++) {
int w = powers[i];
// 倒序遍历，避免重复计算
for (int j = T; j >= 0; j--) {
if (dp[j] == INF) continue; // 当前状态不可达
int next = j + w;
if (next > T) next = T; // 力量超过T的都视为达到T
// 更新新状态的最小兔子数
if (dp[next] > dp[j] + 1) {
dp[next] = dp[j] + 1;
prevState[next] = j; // 记录前一个状态
lastId[next] = i; // 记录最后加入的兔子索引
}
}
}
// 回溯求解方案
vector<int> selected;
int cur = T;
while (cur > 0) {
selected.push_back(lastId[cur] + 1); // 转换为1-indexed编号
cur = prevState[cur];
}
sort(selected.begin(), selected.end());
// 输出结果
cout << dp[T] << endl;
for (int i = 0; i < selected.size(); i++) {
if (i > 0) cout << " ";
cout << selected[i];
}
cout << endl;
return 0;
}
上一题
下一题