题解 CF521D 【Shop】
ShuYuMo
2020-10-19 20:20:13
[MyBlog](https://shuyumo2003.github.io/2020/%E3%80%8C%E9%A2%98%E5%8D%95%E3%80%8DIOI2020%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F%E4%BD%9C%E4%B8%9A-Part-1/#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$。
化归思想，考虑如果只有乘法，那一定是把操作数字从大到小排序，然后以此操作。
考虑操作顺序，最优的操作一定是先赋值，再加法，最后乘法。其中赋值只可能选相应位置最大的赋值，加法也是从大到小考虑。
显然赋值可以直接转化成加法，而加法如果从大到小考虑也可以直接转化成乘法（乘一个实数）。
这样就把所有操作转化成了乘法。 贪心考虑即可。
最后输出有顺序，应按照上面的策略（先赋值，再加法，最后乘法）以此输出（操作顺序）。
## code
{% note info CF521D Shop %}
```cpp
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int _ = 1e5 + 100;
#define LL long long
int read() { int x; scanf("%d", &x); return x; }
int n, m, k;
int v[_];
pair<int, int> Give[_];
vector<pair<int, int > > add[_];
vector<pair<double, int> > mul[_];
vector<pair<double, int> > All;
int T[_];
int id[_];
#define double long double
bool ICMP (const pair<int, int> & x, const pair<int, int> & y) { return (x > y); }
bool ICMP_D(const pair<double, int> & x, const pair<double, int> & y) { return (x > y); }
bool MAGIC(const int &x, const int &y) { return T[x] < T[y]; }
int main(){
k = read(), n = read(), m = read();
for(int i = 1; i <= k; i++) v[i] = read();
for(int i = 1; i <= n; i++){
int type = read(); T[i] = type;
int a = read(), b = read();
if(type == 1){
Give[a] = max(Give[a], make_pair(b, i));
} else if(type == 2){
add[a].push_back(make_pair(b, i));
} else {
mul[a].push_back(make_pair((double)(b), i));
}
}
for(int i = 1; i <= k; i++)
if(Give[i].first)
add[i].push_back(make_pair(Give[i].first - v[i], Give[i].second));
for(int i = 1; i <= k; i++) sort(add[i].begin(), add[i].end(), ICMP);
for(int i = 1; i <= k; i++){
LL now = v[i];
for(int j = 0; j < add[i].size(); j++){
mul[i].push_back(
make_pair(
(double)(now +0ll+ add[i][j].first) / (double)(now),
add[i][j].second
)
); now += add[i][j].first;
}
}
for(int i = 1; i <= k; i++) for(int j = 0; j < mul[i].size(); j++) All.push_back(mul[i][j]);
sort(All.begin(), All.end(), ICMP_D);
int tot = 0;
for(int i = 0; i < All.size(); i++) if(All[i].first > 1) { tot++; }
tot = min(tot, m);
for(int i = 1; i <= tot; i++) id[i] = All[i - 1].second;
sort(id + 1, id + 1 + tot, MAGIC); printf("%d\n", tot);
for(int i = 1; i <= tot; i++) printf("%d%c", id[i], " \n"[i == n]);
return 0;
}
```
{% endnote %}