蓝桥杯2023年第十四届省赛真题-买瓜--C语言题解
目录
(图片来源网络,侵删)
蓝桥杯2023年第十四届省赛真题-买瓜
题目描述
输入格式
输出格式
样例输入
样例输出
提示
【思路解析】
【代码实现】
蓝桥杯2023年第十四届省赛真题-买瓜
时间限制: 3s 内存限制: 320MB 提交: 796 解决: 69
题目描述
小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜,每个瓜的重量为 Ai 。
小蓝刀功了得,他可以把任何瓜劈成完全等重的两份,不过每个瓜只能劈一刀。
小蓝希望买到的瓜的重量的和恰好为 m 。
请问小蓝至少要劈多少个瓜才能买到重量恰好为 m 的瓜。如果无论怎样小蓝都无法得到总重恰好为 m 的瓜,请输出 −1 。
输入格式
输入的第一行包含两个整数 n, m,用一个空格分隔,分别表示瓜的个数和小蓝想买到的瓜的总重量。
第二行包含 n 个整数 Ai,相邻整数之间使用一个空格分隔,分别表示每个瓜的重量。
输出格式
输出一行包含一个整数表示答案。
样例输入
复制
3 10 1 3 13
样例输出
复制
2
提示
对于 20% 的评测用例,∑n≤10;
对于 60% 的评测用例,∑n≤20;
对于所有评测用例,1 ≤n≤30,1≤ Ai ≤ 109 ,1 ≤ m ≤ 10^9
【思路解析】
这道题是一个很简单的递归可能性的罗列,但是每次递归有三个情况,则时间复杂度为O(3^N),时间复杂度过高,所以需要在递归过程中除掉那些完全不可能的解,使复杂度降低。
【代码实现】
#include int n = 0, m = 0, nums[30], min = 100; long suf[31]; int dfs(int i, double sum, int c) { if (c >= min) return 100; // 劈瓜的次数大于等于最小值,即使能满足要求m也没有意义,因为它不是最小的 if (sum == m) { min = c; return c; } if (sum > m) return 100; // 如果当前sum大于m,即可提前结束 if (i == n) { return 100; //此时已经使用了所有西瓜,也无法满足,直接排除掉 } if (suf[i] + sum b? b :a; } int main(){ scanf("%d %d", &n, &m); int i = 0; for (i = 0; i = 0; i--) { suf[i] = suf[i + 1] + nums[i]; } int m = dfs(0, 0, 0); if (m == 100) printf("-1"); else{ printf("%d\n",m); } return 0; }
文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。