[ABC289G] Shopping in AtCoder store

· · 题解

更好的阅读体验

题目描述

题目传送门

思路

先将 B 和 C 从小到大排序。显然的，每一个 P_i 都可以表示为 B_j + C_i。称 B_j 为 C_i 的最优决策。

然后还可以发现答案具有单调性，如果 B_j 是 C_i 的最优决策，那么 B_k(B_k < B_j) 不可能是 C_{l} < C_i 的最优决策。

于是我们可以进行分治。

具体的，就是可以在分治的子任务中来选择最排完序中间的一个客人作为购买的最后一个人，然后枚举商品计算贡献，最后递归进去就好了。

具体看代码。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10;

ll Ans[MAXN], B[MAXN];
pair<ll, int> C[MAXN];
int N, M;

void solve(int l1, int r1, int l2, int r2) {
    if (l1 > r1) return;
    int mid = l1 + r1 >> 1;
    ll ans = 0, pos = 0;
    for (int i = r2; i >= l2; i--) {
        if ((B[i] + C[mid].first) * (N - i + 1) > ans) {
            ans = (B[i] + C[mid].first) * (N - i + 1);
            pos = i;
        }
    }
    Ans[C[mid].second] = ans;
    solve(l1, mid - 1, pos, r2);
    solve(mid + 1, r1, l2, pos);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for (int i = 1; i <= N; i++) cin >> B[i];
    for (int i = 1; i <= M; i++) {
        cin >> C[i].first;
        C[i].second = i;
    }
    sort(B + 1, B + 1 + N);
    sort(C + 1, C + 1 + M);
    solve(1, M, 1, N);
    for (int i = 1; i <= M; i++) cout << Ans[i] << " ";
    return 0;
}