[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;
}