# E

# 题目大意

给定一个长度为 $N$ 的序列： $A = (A_1, A_2, ..., A_N)$ 和 $B = (B_1, B_2, ..., B_N)$ 。
设 $S$ 是大小为 $K$ 的 $\lbrace1, 2, \dots, N\rbrace$ 的子集。求以下表达式的最小可能值：

$$(\max_{i \in S} A_i) \times (\sum_{i \in S} B_i)$$

给你 $T$ 个测试用例，请逐个求解。

# 数据范围

• $1 \le T \le 2 \times 10^5$
• $1 \le K \le N \le 2 \times 10^5$
• $1 \le A_i, B_i \le 10^6$

# 题解

将 $A$ 序列按从小到大的顺序排。
排完序之后，显然，$A_i~(i \in [1,k-1])$ ，不可能会被选上
那么我们只需要从 $A_k$ 枚举到 $A_n$，这个范围内都是满足题意的、可以被选的 $A_i$.

那么问题来了？$\sum_{i \in S} B_i$ 怎么办呢？
我们可以用优先队列维护，先将前 $B_1 \to B_{k-1}$，$push$ 进队列并用一个 sum 累加和。
而对于可以选择的 $A_i,(i \in [k, n])$，当 $A_i$ 被选中时，$B_i$ 即要加入和，那么这时会有两种情况：

• heap.size() == k
  • 那么我们就要先弹出一个最大的来，代表不选它。
• heap.size() == k - 1
  • 直接 $push$ 进队列，算新的和即可。
    描述思路有点抽象，可以结合代码理解。
    

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

    #define int long long using namespace std; typedef pair<int, int> PII; const int N = 2e5 + 10; int n, k; PII num[N]; bool cmp(PII x, PII y) { return x.first < y.first; } void solve () { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> num[i].first; for (int i = 1; i <= n; i++) cin >> num[i].second; sort(num + 1, num + n + 1, cmp); priority_queue<int> heap; int ans = LONG_LONG_MAX, sum = 0; for (int i = 1; i <= k - 1; i++) { heap.push(num[i].second); sum += num[i].second; } for (int i = k; i <= n; i++) { if (heap.size() == k) { sum -= heap.top(); heap.pop(); } heap.push(num[i].second), sum += num[i].second; ans = min(ans, sum * num[i].first); } cout << ans << endl; }