题意 题目链接。 有两组物品，每个物品都有一定的价值，你需要选择若干个物品，收益为两组物品中价值和较少的那组物品的价值和减去所选取的所有物品数。使收益最大化。 解析 发现肯定优先选择价值高的物品。 发现如果已经选择了若干个物品，接下来那个物品只有选择当前总价值低的那一组才有可能有更优解。 由上，本题可以用双指针解决。对于两组物品分别用一个指针维护，…

题意 题目链接。 给定一个序列，包含 $n$ 个有重量和价值的物品。需要找出一个连续区间，可以选择其中的至多 $w$ 个物品令其重量减半（向上取整）而价值不变，然后该区间重量和须不大于 $k$。求满足这样条件的总价值最大的区间。 解析 求区间最大价值容易想到双指针。考虑如何维护重量减半（以下简称打折）的 $w$ 个物品。 由于元素会有重复，考虑用两…