題目要求

P1094題目鏈接

分析

經(jīng)典的貪心思想，為什么是貪心呢？請看這位大佬的博客講解，他講的真的很好，orz。

我講一下怎么用貪心吧。

其實貪心一般與排序相關(guān)，因為總要獲取局部最優(yōu)解嘛，不是最大就是最小，這里也是先將數(shù)據(jù)序列排個序，直接用Arrays.sort()即可。

然后就是使用雙指針來處理啦！一個在索引0處向末端移動，另一個在末端向索引0處移動。

怎么移動呢？比較指針（其實是int類型的index）指向的值，

• 二者之和大于價格上限就說明只能選取最大值并丟棄最小值，所以low指針不動，high指針左移一位。
• 二者之和小于等于價格上限就說明當前的局部最優(yōu)解是最大值+最小值（因為至多選兩個），所以low右移，high左移。

要注意最終的條件，while循環(huán)保持的條件是low<high，但終止可能是兩種情況，一定要注意：

• low == high，這是因為最后一次還剩一個值，low == high。
• low > high，這是因為最后一次二者剛好湊對兒。

在low == high的時候，由于還剩一個沒選，所以需要把counter++。

然后打印結(jié)果即可。

注意 --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);} }

總結(jié)

以上是生活随笔為你收集整理的贪心の纪念品分组（洛谷P1094题题解，Java语言描述）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。