纪念品分组-题解（Java代码）

解题思路:

根据题意乍一看是背包问题，在读题 发现不是，仔细读题 纪念品价值相对均衡 考虑到归并排序的模板定义两个指针

一个指向数组的头，一个指向数组的尾 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);

                                                 }