首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#13155

小白兔拔萝卜 小白兔拔萝卜,但是它的力量有限,太大的萝卜它拔不动。于是它叫来了一群小伙伴…… 本题就请你根据小白兔们的力量和拔出这个萝卜需要的力量,告诉小白兔,…

小白兔拔萝卜

小白兔拔萝卜,但是它的力量有限,太大的萝卜它拔不动。于是它叫来了一群小伙伴……

本题就请你根据小白兔们的力量和拔出这个萝卜需要的力量,告诉小白兔,它最少需要哪些伙伴能拔出这只大萝卜。

时间限制:7000,内存限制:65536

输入描述

输入在第一行里给出两个不超过 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.
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//答案来源于AI #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;climits&gt; using namespace std; const int INF = 10000; int main() {     int n, T;     cin &gt;&gt; n &gt;&gt; T;     vector&lt;int&gt; powers(n);     long long total = 0;     for (int i = 0; i &lt; n; i++) {         cin &gt;&gt; powers[i];         total += powers[i];     }     // 处理总力量不足的情况     if (total &lt; T) {         cout &lt;&lt; "0" &lt;&lt; endl;         cout &lt;&lt; "Suan4 le ba, hai2 cha4 " &lt;&lt; T - total &lt;&lt; "." &lt;&lt; endl;         return 0;     }     // 动态规划数组,dp[j]表示达到力量j所需的最少兔子数     vector&lt;int&gt; dp(T + 1, INF);     // 记录状态转移路径     vector&lt;int&gt; prevState(T + 1, -1);     vector&lt;int&gt; lastId(T + 1, -1);          // 初始状态:0力量需要0只兔子     dp[0] = 0;     // 动态规划过程     for (int i = 0; i &lt; n; i++) {         int w = powers[i];         // 倒序遍历,避免重复计算         for (int j = T; j &gt;= 0; j--) {             if (dp[j] == INF) continue;  // 当前状态不可达                          int next = j + w;             if (next &gt; T) next = T;  // 力量超过T的都视为达到T                          // 更新新状态的最小兔子数             if (dp[next] &gt; dp[j] + 1) {                 dp[next] = dp[j] + 1;                 prevState[next] = j;  // 记录前一个状态                 lastId[next] = i;     // 记录最后加入的兔子索引             }         }     }     // 回溯求解方案     vector&lt;int&gt; selected;     int cur = T;     while (cur &gt; 0) {         selected.push_back(lastId[cur] + 1);  // 转换为1-indexed编号         cur = prevState[cur];     }     sort(selected.begin(), selected.end());     // 输出结果     cout &lt;&lt; dp[T] &lt;&lt; endl;     for (int i = 0; i &lt; selected.size(); i++) {         if (i &gt; 0) cout &lt;&lt; " ";         cout &lt;&lt; selected[i];     }     cout &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。