贪心の纪念品分组（洛谷P1094题题解，Java语言描述）

题目要求

P1094题目链接

分析

经典的贪心思想，为什么是贪心呢？请看这位大佬的博客讲解，他讲的真的很好，orz。

我讲一下怎么用贪心吧。

其实贪心一般与排序相关，因为总要获取局部最优解嘛，不是最大就是最小，这里也是先将数据序列排个序，直接用Arrays.sort()即可。

然后就是使用双指针来处理啦！一个在索引0处向末端移动，另一个在末端向索引0处移动。

怎么移动呢？比较指针（其实是int类型的index）指向的值，

• 二者之和大于价格上限就说明只能选取最大值并丢弃最小值，所以low指针不动，high指针左移一位。
• 二者之和小于等于价格上限就说明当前的局部最优解是最大值+最小值（因为至多选两个），所以low右移，high左移。

要注意最终的条件，while循环保持的条件是low<high，但终止可能是两种情况，一定要注意：

• low == high，这是因为最后一次还剩一个值，low == high。
• low > high，这是因为最后一次二者刚好凑对儿。

在low == high的时候，由于还剩一个没选，所以需要把counter++。

然后打印结果即可。

注意 --i 和 ++i 比 i-- 和 i++ 快！

再就是对于Java党，顶多读30000次，所以Scanner必定不会炸，所以放心用就好，Scanner毕竟简单一些。

AC代码（Java语言描述）

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int limit = scanner.nextInt(), num = scanner.nextInt();
        int[] gifts = new int[num];
        for (int i = 0; i < num; i++) {
            gifts[i] = scanner.nextInt();
        }
        scanner.close();
        Arrays.sort(gifts);
        int counter= 0, i = 0, j = num-1;
        while (i < j) {
            if (gifts[i] + gifts[j] > limit) {
                --j;
                ++counter;
            } else {
                ++i;
                --j;
                ++counter;
            }
        }
        if (i == j) {
            ++counter;
        }
        System.out.println(counter);
    }
}