原题链接：蓝桥杯2023年第十四届省赛真题-买瓜
参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | import java.util.Arrays;import java.util.Scanner;public class Main{ static int n, m, weight[], res = 100; static long suf[];//后缀和 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); weight = new int[n]; for (int i = 0; i < n; i++) weight[i] = scanner.nextInt(); reverseSort(weight);//题目要求最小刀数，提前对重量组降序排列（剪枝），否则官网有三个样例过不了 suf = new long[n + 1];// 后缀和，要开long不然会爆 for (int i = n - 1; i >= 0; i--) suf[i] = suf[i + 1] + (long) weight[i]; dfs(0, 0, 0); if (res == 100) System.out.println(-1); else System.out.println(res); } static void dfs(int pos, double sum, int cnt)//层数，重量和，刀数 { if(sum == m) { res = Math.min(res, cnt); return; } if(pos >= n || cnt >= res || sum > m || sum + suf[pos] < m) return; for (int j = pos; j < n; j++) { sum += weight[j]; //整个西瓜拿走 dfs(j + 1, sum, cnt); sum -= weight[j] / 2.0; //拿走一半 dfs(j + 1, sum, cnt + 1); sum -= weight[j] / 2.0; //不拿走 } } static void reverseSort(int[] arr) { Arrays.sort(arr); int i = 0; int j = arr.length - 1; while(i < j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; i++; j--; } }} |
0 分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复