一、题意

给定n个物品的大小a[maxn]，每个背包的容量M，并且每个背包最多只能装2个物品。输出装下所有物品至少需要的背包数目。

二、解析

一看就是典型的乘船问题（贪心问题中的一种）。

由于只能装2个物品，因此我们首先将物品按大小排序，然后通过双指针指向一头一尾。
头指针指向的是当前最小的物品，我们总是贪心地希望它和尽量大地物品装一起，也就是尾指针指向的物品。若这两个物品加起来可以装进背包，则就这么装（因为这是最赚的装法），然后指针分别都向中间移动，ans++；若装不下，则对于大的那个物品来说，连最小的都不能和它一起装下，那么它必然只能自己一个人装一个背包，所以尾指针向前移动，头指针不动，ans++。

这样就能在O(n)时间得到结果了。

三、代码

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 5;
int kase, n, M, a[maxn];

int main() {
    cin >> kase;
    while(kase --) {
        cin >> n >> M;
        for(int i = 0; i < n; i ++) cin >> a[i];
        sort(a, a + n);
        int i = 0, j = n - 1, ans = 0;
        while(i <= j) {
            if(a[i] + a[j] <= M) ans ++, i ++, j --;
            else ans ++, j --;
        }
        cout << ans << endl;
        if(kase) cout << endl;
    }
}

四、归纳

  • 一种比较简单的贪心问题题型，做过就会了。