Java实现 蓝桥杯 算法训练 纪念品分组
2023-09-14 08:58:17 时间
问题描述
元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值 相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品,并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时 间内发完所有纪念品,乐乐希望分组的数目最少。
你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。
输入格式
输入包含n+2行:
第1行包括一个整数w,为每组纪念品价格之和的上限。
第2行为一个整数n,表示购来的纪念品的总件数。
第3~n+2行每行包含一个正整数pi (5 <= pi <= w),表示所对应纪念品的价格。
输出格式
输出仅一行,包含一个整数,即最少的分组数目。
样例输入
100
9
90
20
20
30
50
60
70
80
90
样例输出
6
数据规模和约定
50%的数据满足:1 <= n <= 15
100%的数据满足:1 <= n <= 30000, 80 <= w <= 200
import java.util.Arrays;
import java.util.Scanner;
public class jinianpinfenzu {
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
int w = sc.nextInt();
int n = sc.nextInt();
int [] num = new int [n+1];
for (int i = 1; i < num.length; i++) {
num[i]=sc.nextInt();
}
Arrays.sort(num);
int count = 0;
for (int i = 1,j=num.length-1; i<=j;) {
if(i==j){
count++;
break;
}
if(j-i==1){
count++;
break;
}
if(num[i]+num[j]<=w){
count++;
i++;
j--;
}
else{
j--;
count++;
}
}
System.out.println(count);
}
}
相关文章
- java bufferedwriter 编码,Java BufferedWriter对象与utf-8
- java基础题目_40道java基础练习题,你会卡在哪道题?
- 在线学习Java的几个网站,别再盲目学习java了![通俗易懂]
- java无法获取服务器上路径,JAVA获取服务器路径的步骤
- java 随机数算法_Java随机数算法原理与实现方法实例详解
- java笛卡尔积算法_Java 笛卡尔积算法的简单实现
- Java版五子棋小游戏(java控制台)
- Java使用JDBC向数据库存取二进制数据(如图片,视频,音频等)
- java executeupdate_Java自学-JDBC execute与executeUpdate的区别
- java测试案例编写方法_java实现自动化测试实例
- 【Java】函数式编程与JUC编程问题?函数式编程如何解决线程安全问题?
- java一维数组
- 快速搭建Java 17环境并玩转Record特性
- java获得PID详解编程语言
- Java调用JavaScript实现字符串计算器详解编程语言
- java学习笔记04–数组详解编程语言
- Java中的回车换行符/n /r /t详解编程语言
- Java问题-java进程占用内存过高,排查原因详解编程语言
- MySQL数据库开发实践:用 Java 开发中文应用(mysql中文java)
- 极速搭建Java连接SqlServer数据库(java连接sqlserver)
- 清理使用 Java 清理Redis过期数据(redisjava过期)
- Exploring the Power of Java with MongoDB for Enhanced Data Management(java与mongodb)
- Java Redis实例学习与应用(java redis实例)
- Java搭配MySQL,实现创新跳跃的可能(java 与mysql)
- Java配置Oracle实现稳定的跨平台数据库连接(java配置oracle)