CF521D Shop 题解

CF521D Shop

题意

• 有 $k$ 个正整数 $a_{1\dots k}$。
• 有 $n$ 个操作，每个操作给定正整数 $b$，有三种可能：将 $a_i$ 赋值为 $b$，将 $a_i$ 加上 $b$，将 $a_i$ 乘以 $b$。
• 你可以从 $n$ 个操作中选择最多 $m$ 个操作，并按照一定顺序执行。
• 你的目标是最大化 $\prod_{i=1}^k a_i$ 的值。
• $k,n \le 10^5$。

题解

首先赋值可以转化成加法，只是要注意赋值必须在加法之前。

其次加法可以转化成乘法，不过必须按照从大到小贪心的转化，且加法也要在乘法之前。

对于加法转乘法，有一个麻烦一点的等价方法是，同样对每个数从大到小贪心的选择，只不过动态维护。

一开始假设所有乘法操作都要选，如果乘法操作的个数多于 $m$ 个，则去掉多出来贡献最小的。

对 $k$ 个数上的加法操作进行排序，我们要从大到小贪心的选择，可以用 $k$ 个指针维护。

用一个堆，每次取出贡献最大的加法操作，然后与贡献最小的乘法操作相比较。若加法操作的贡献更大，则去掉这个贡献最小的乘法操作，同时加入贡献最大的加法操作；否则说明此时达到最优解。

若 $n,m,k$ 同阶，则总时间复杂度为 $\mathcal O(n \log n)$。

代码

const int N = 1e5 + 7;
int n, m, k, s;
ui t[N];
ll a[N], b;
pair <ll, int> v1[N];
vector <pair <ll, int> > v2[N], v3;
pq <pair <ld, int> > q;
vi ans;

inline void print() {
	for (int i = 1; i <= k; i++) {
		for (ui j = 0; j < t[i]; j++)
			if (v2[i][j].se < 0) ans.pb(-v2[i][j].se);
		for (ui j = 0; j < t[i]; j++)
			if (v2[i][j].se > 0) ans.pb(v2[i][j].se);
	}
	while (v3.size()) ans.pb(v3.back().se), v3.pop_back();
	print(ans.size());
	for (auto x : ans) print(x, ' ');
}

inline void get(int x) {
	if (t[x] < v2[x].size())
		q.push(mp(1.0L * v2[x][t[x]++].fi / a[x], x));
}

int main() {
	rd(k), rd(n), rd(m);
	for (int i = 1; i <= k; i++) rd(a[i]);
	for (int i = 1, o, x; i <= n; i++) {
		rd(o), rd(x), rd(b);
		if (o == 1) v1[x] = max(v1[x], mp(b, i));
		if (o == 2) v2[x].pb(mp(b, i));
		if (o == 3) v3.pb(mp(b, i));
	}
	for (int i = 1; i <= k; i++) {
		if (v1[i].fi > a[i])
			v2[i].pb(mp(v1[i].fi - a[i], -v1[i].se));
		sort(v2[i].begin(), v2[i].end());
		reverse(v2[i].begin(), v2[i].end());
		s += v2[i].size();
	}
	sort(v3.begin(), v3.end());
	reverse(v3.begin(), v3.end());
	while ((int)v3.size() > m) v3.pop_back();
	if (s + (int)v3.size() <= m) {
		for (int i = 1; i <= k; i++) t[i] = v2[i].size();
		return print(), 0;
	}
	for (int i = 1; i <= k; i++) get(i);
	for (int i = v3.size(); i < m; i++) {
		int x = q.top().se;
		q.pop(), a[x] += v2[x][t[x]-1].fi, get(x);
	}
	while (v3.size()) {
		int x = q.top().se;
		ll b1 = v2[x][t[x]-1].fi, b2 = v3.back().fi;
		if (b1 <= a[x] * (b2 - 1)) break;
		q.pop(), v3.pop_back(), a[x] += b1, get(x);
	}
	while (q.size()) {
		int x = q.top().se;
		q.pop(), --t[x];
	}
	return print(), 0;
}