东莞网站建设服务商,网站制作的公司哪家比较好,订阅号 微网站,重庆网站建设网站题目 又到了一年的末尾#xff0c;项目组让小明负责新年晚会的小礼品发放工作。为使得参加晚会的同时所获得的小礼品价值相对平衡#xff0c;需要把小礼品根据价格进行分组#xff0c;但每组最多只能包括两件小礼品#xff0c;并且每个分组的价格总和不能超过一个价格上限。…题目 又到了一年的末尾项目组让小明负责新年晚会的小礼品发放工作。为使得参加晚会的同时所获得的小礼品价值相对平衡需要把小礼品根据价格进行分组但每组最多只能包括两件小礼品并且每个分组的价格总和不能超过一个价格上限。为了保证发放小礼品的效率小明需要找到分组数目最少的方案。 你的任务是写一个程序找出分组数最少的分组方案并输出最少的分组数目。 输入 第一行数据为分组礼品价格之和的上限 第二行数据为每个小礼品的价格按照空格隔开每个礼品价格不超过分组价格和的上限 输出 输出最小分组数量 示例1: 输入: 5 1 2 5 输出: 2 思路 最多只能分两个礼品要求最小方案数。先将输入nums按从小到大排序以数据为例1 2 3 3 5 8假设不超过8让left指向第一个礼物1right指向最后一个礼物8 计算当前礼物价值819超过限制8只能单独分一组right- -res1 left1right5和为6可以分为一组leftright- -,res2 left2,right3,可以分为一组leftright- -,res3 left3right3指向的同一个值单独分一组即可res4 上述过程可以用队列或者双指针模拟实现。 题解
package hwod;import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;public class GiftGroup {public static void main(String[] args) {Scanner sc new Scanner(System.in);int max sc.nextInt();sc.nextLine();int[] nums Arrays.stream(sc.nextLine().split( )).mapToInt(Integer::parseInt).toArray();System.out.println(giftGroup(nums, max));System.out.println(giftGroup2(nums, max));}private static int giftGroup(int[] nums, int max) {Arrays.sort(nums);LinkedListInteger queue new LinkedList();for (int num : nums) {queue.addLast(num);}int res 0;while (queue.size() 1) {int cur queue.peekLast() queue.peekFirst();queue.removeLast();if (cur max) {queue.removeFirst();}res;}return queue.isEmpty() ? res : res 1;}private static int giftGroup2(int[] nums, int max) {Arrays.sort(nums);int left 0, right nums.length - 1, res 0;while (left right) {int cur nums[right] nums[left];right--;res;if (cur max) {left;}}return leftright?res1:res;}
}
推荐
如果你对本系列的其他题目感兴趣可以参考华为OD机试真题及题解JAVA查看当前专栏更新的所有题目。
