题解 CF521D 【Shop】
xht
2020-01-16 01:00:42
> [CF521D Shop](https://codeforces.com/contest/521/problem/D)
## 题意
- 有 $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)$。
## 代码
```cpp
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;
}
```