算法
(贪心,排序) $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;
}
使用贪心策略时,$a$ 可能单独为一组,此时 $a$ 就不存在“同伴物品” $b$,这种情况证明中是不是没有考虑到?
可以