深圳营销型网站建设设计公司,上海市建设工程咨询网,漫威网页制作教程,如何注册网站的名字目录
蓝桥杯2023年第十四届省赛真题-买瓜
题目描述
输入格式
输出格式
样例输入
样例输出
提示
【思路解析】
【代码实现】 蓝桥杯2023年第十四届省赛真题-买瓜
时间限制: 3s 内存限制: 320MB 提交: 796 解决: 69
题目描述
小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个…目录
蓝桥杯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≤301≤ Ai ≤ 109 1 ≤ m ≤ 10^9
【思路解析】
这道题是一个很简单的递归可能性的罗列但是每次递归有三个情况则时间复杂度为O(3^N)时间复杂度过高所以需要在递归过程中除掉那些完全不可能的解使复杂度降低。
【代码实现】
package LQB;import java.util.Scanner;/*** ProjectName: study3* FileName: Ex4* author:HWJ* Data: 2023/9/17 21:54*/
public class Ex4 {static double[] subs; // subs[i]表示为西瓜i -西瓜n-1的西瓜质量和用于对递归的降低可能性static double m;static int n;static int min 40; // 因为n最大为30所以最多劈瓜30次static double[] weights; // weights[i]表示为第i个西瓜的质量public static void main(String[] args) {Scanner input new Scanner(System.in);n input.nextInt();m input.nextInt();weights new double[n];subs new double[n];for (int i 0; i n; i) {weights[i] input.nextInt();}subs[n - 1] weights[n - 1];for (int i n - 2; i 0; i--) {subs[i] subs[i 1] weights[i];}int p dfs(0, 0, 0);System.out.println(p Integer.MAX_VALUE ? -1 : p);}// sum 表示现在搞定了多少西瓜 index 表示现在对第几个西瓜做决策 have表示现在已经劈了几次瓜了public static int dfs(double sum, int index, int have) {if (have min) { // 如果此时虽然满足要求但他大于了当前的最优情况他不可能是最优解直接排除掉return Integer.MAX_VALUE;}if (sum m) { // 达到满足要求min have; // 更新最小情况。return have;}if (sum m) {return Integer.MAX_VALUE; // 此时不加任何西瓜 重量也已经超过了需要的重量所以直接排除}if (index n) {return Integer.MAX_VALUE; //此时已经使用了所有西瓜也无法满足直接排除掉}if (subs[index] sum m) {return Integer.MAX_VALUE; // 此时加上后面所有的西瓜也不满足条件所以没有必要再递归了}int p1 dfs(sum weights[index], index 1, have);int p2 dfs(sum weights[index] / 2.0, index 1, have 1);int p3 dfs(sum, index 1, have);return Math.min(p1, Math.min(p2, p3));}}
