题解：AT_abc376_e [ABC376E] Max × Sum

· · 题解

题目翻译

给你两个长度为 N 的序列 A 和 B。再给你一个整数 K，让你求对于集合 \lbrace\ 1,\ 2,\ \dots,\ N\ \rbrace 的每一个长度为 K 的子集 S，求 \displaystyle\ \left(\max_{i\ \in\ S}\ A_i\right)\ \times\ \left(\sum_{i\ \in\ S}\ B_i\right) 的最小值。有 T 组测试数据。

思路

子集是不一定连续的，在这个问题中，顺序也不重要，所以我们可以把序列按 A 从小到大排序。值得注意的是，A_i 和 B_i 是对应的，所以需要放到一个结构体里面，不然排完序之后就乱了。

排序的好处是我们在计算 A 中前 i 个元素选出 K 个数（第 i 个必须选）里面的最大值的时候可以直接用 A_i，时间复杂度 O(1)。

然后我们的问题就只剩下一点点了。需要求和的那部分怎么算呢？因为要求最小值，所以肯定希望这个和越小越好。那最小值怎么维护呢？我在比赛的时候想到了动态规划，但是时间复杂度 O(N\cdot K)，空间复杂度在压维了之后是 O(K)，肯定会超时。

怎么优化呢？前面的思路都没有问题，就卡在这一步了。事实上，有个好东西叫堆，它可以帮助我们解决这个问题。不会手写堆可以用 STL 里面的优先队列。

建一个大根堆，先把 B_1,B_2,\dots,B_{K-1} 放进去。然后对于 i=K,K+1,\dots,N，考虑把它放进堆里会不会产生更好的答案。我们维护一个变量 sum，它的初始值为 B 数组中第 1 至第 K-1 个元素之和。每一次，B_i 入队，用队列中所有数之和乘以最大值（前面说过怎么算）更新答案。然后，我们把堆中最大的那个数（即堆顶）弹出去。sum 的更新方式为：先加上 B_i，再减去堆顶元素的值。

于是这样就 AC 了。