MyBlog

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 %}

#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 %}