算法

(贪心,排序) $O(nlogn)$

直觉上讲，分组的时候应该尽可能让每一组的价值之和大一些。

由此得到如下算法：

• 将所有物品按价值排序；
• 从小到大枚举每个物品，每次给当前物品找一个价值尽可能大的且总价值没有超过上限的“同伴物品”，将两个物品分在一组，这一步可以使用双指针算法优化到 $O(n)$。
• 这样求出的组数就是最小值。

下面给出证明。这里可以使用“调整法”：

• 假设最优解的分组方式和由上述算法得到的分组方式不同。那么我们考虑从后往前第一个分组不同的数，记为 $a$，假设由上述算法得到的“同伴物品”是 $b$，那么：

  • 如果在最优解中，$a$ 单独一组，那么可以直接将 $b$ 从原组中取出，和 $a$ 放在一起，这样并没有增加组数；
  • 如果在最优解中，$a$ 和 $c$ 放在一起，由上述算法可知，$c \le b$，那么我们可以将 $b$ 和 $c$ 所在位置交换，交换后两组的价值之和都没有超过上限，且这样也没有增加组数。
  • 因此通过上述调整，我们可以在不增加组数的情况下，将最优解的分组方式调整成和上述算法相同，且这样的调整方式可以一直进行下去，直到两个方案相同为止。

• 因此我们可以在不增加组数的情况下，将最优解的方案调整成上述算法得到的方案，因此上述算法可以得到最优解。

时间复杂度

排序是算法瓶颈，因此时间复杂度是 $O(nlogn)$。

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 30010;

int n, m;
int w[N];
bool st[N];

int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; i ++ ) cin >> w[i];

    sort(w, w + n);

    int res = 0;
    for (int i = 0, j = n - 1; i < n; i ++ )
    {
        if (st[i]) continue;
        while (j >= i && (st[j] || w[i] + w[j] > m)) j -- ;
        st[i] = st[j] = true;
        res ++ ;
    }

    cout << res << endl;
    return 0;
}