链接：

 

题意：

给定N（N≤1e5）个物品的重量Li，背包的容量M，同时要求每个背包最多装两个物品。

求至少要多少个背包才能装下所有的物品。

 

分析：

排序，然后贪心选择即可。如果能和物品A一起装入背包的另一个物品B有多个，则应该选择最重的一个物品B。

证明：

若不是选择物品B，而是选择物品C（C的重量小于B），则总的背包数不仅没有减少，反而可能增加。

 

代码：

1 #include 
     
       2 #include 
      
        3 using namespace std; 4  5 int a[100000+5]; 6  7 int main(){ 8     int T, n, b; 9     scanf("%d", &T);10     while(T--){11         scanf("%d%d", &n, &b);12         for(int i = 0; i < n; i++) scanf("%d", &a[i]);13         sort(a, a + n);14 15         int remain = n;16         for(int L = 0, R = n - 1; L < R; R--){17             if(a[L] + a[R] <= b) L++, remain -= 2;18         }19         printf("%d\n", (n + remain) / 2);20         if(T) printf("\n");21     }22     return 0;23 }