CF521D Shop 题解

jiangly · 2019-11-20 11:31:37 · 题解

题意

给定 k (1\le k\le 10^5) 个数 a_1,a_2,\ldots,a_k，有 n (1\le n\le 10^5) 个操作，每个操作为将 a_{j_i} 赋值为 / 加上 / 乘上 b_i。在所有操作中选最多 m 个按一定顺序执行，使得所有数的乘积最大。

题解

首先如果确定了执行的操作，执行顺序一定为赋值、加、乘。赋值操作只保留最大的，并可以转化为加法。每个数的加法操作按从大到小顺序排序后可以转化为乘法。最后将所有乘法操作从大到小排序选前 m 个即可。

代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int N = 1E5;
int k, n, m;
int a[N], t[N], j[N], b[N];
pair<int, int> as[N];
vector<pair<int, int>> add[N];
vector<pair<long double, int>> mul;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> k >> n >> m;
    for (int i = 0; i < k; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i) {
        cin >> t[i] >> j[i] >> b[i];
        --j[i];
        switch (t[i]) {
            case 1:
                as[j[i]] = max(as[j[i]], make_pair(b[i], i));
                break;
            case 2:
                add[j[i]].emplace_back(b[i], i);
                break;
            case 3:
                mul.emplace_back(b[i], i);
        }
    }
    for (int i = 0; i < k; ++i)
        if (as[i].first > a[i])
            add[i].emplace_back(as[i].first - a[i], as[i].second);
    for (int i = 0; i < k; ++i) {
        sort(add[i].begin(), add[i].end(), greater<pair<int, int>>());
        LL v = a[i];
        for (const auto &p : add[i]) {
            mul.emplace_back(1.0L * (v + p.first) / v, p.second);
            v += p.first;
        }
    }
    sort(mul.begin(), mul.end(), greater<pair<long double, int>>());
    int x = min(m, (int)mul.size());
    sort(mul.begin(), mul.begin() + x, [&](const auto &lhs, const auto &rhs) {return t[lhs.second] < t[rhs.second];});
    cout << x << "\n";
    for (int i = 0; i < x; ++i)
        cout << mul[i].second + 1 << " \n"[i == x - 1];
    return 0;
}