解题思路:
根据题意乍一看是背包问题,在读题 发现不是,仔细读题 纪念品价值相对均衡 考虑到归并排序的模板定义两个指针
一个指向数组的头,一个指向数组的尾 start 和 end 指针
然后题中说的每个数据不会超过 上限 题意就非常清楚了
注意事项:
需要注意的是两个指针相撞的几种情况,循环结束要执行的代码
参考代码:、
public static void f2() {
Scanner sc = new Scanner(System.in);
int max = sc.nextInt(); //上限
int n = sc.nextInt(); //礼品数
int[] arr = new int[n];
for (int i = 0; i < arr.length; i++) {
arr[i] = sc.nextInt();
}
Arrays.sort(arr); // 从小到大排序
int res = 0; //用来存放结果
//定义两个指针 归并排序思想
int start = 0;
int end = arr.length-1;
while(end > start) {
if(arr[end]+arr[start]>max) {
end--;
res++;
}else {
end--;
start++;
res++;
}
}
if(end == start) {
res++;
}
System.out.println(res);
}
0.0分
3 人评分