Codeforces

Luogu

分析

首先可以知道,我们执行操作的顺序一定是赋值 $\to$ 加 $\to$ 乘。

先考虑只有乘的情况。因为我们要最大化所有数的积,因此直接选最大的 $m$ 个即可。

再考虑有加的情况,我们想办法把加转化为乘。对于每一个位置,我们把对它的加操作按权值从大到小排序,显然我们选的会是一段前缀,因此我们可以转化为一些乘 $\displaystyle\frac{\sum_{i=1}^xb_i}{\sum_{i=1}^{x-1}b_i}$ 的操作。

最后考虑有赋值的情况。显然我们每个位置至多只会赋值一次,因此选最大的那个,看做一个加 $\Delta$ 的操作即可。

把所有操作都转化为乘之后,我们只要贪心选最大的就好了。

一些细节:

  • 分数运算会爆 long long。因为我们只要比大小,因此可以把所有分数减 $1$。
  • 转换后可能会有乘了会变小的,这些是不能选的。
  • 输出时要把选的操作按赋值 $\to$ 加 $\to$ 乘的顺序排好序再输出。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int k,m,n,a[N],mxa[N],mxid[N];
vector<pair<int,int> > add[N],ans;
struct node { ll x,y; int id,op; };
vector<node> mul;

inline int cmp1(pair<int,int> x,pair<int,int> y) { return y<x; }
inline int cmp2(node x,node y) { return x.x*y.y>x.y*y.x; }

#define fi first
#define se second

int main() {
    k=read(),n=read(),m=read();
    for (re int i=1;i<=k;++i) a[i]=read();
    for (re int i=1;i<=n;++i) {
        int op=read(),x=read(),b=read();
        if (op==1&&b>mxa[x]) mxa[x]=b,mxid[x]=i;
        if (op==2) add[x].push_back(make_pair(b,i));
        if (op==3) mul.push_back((node){b-1,1,i,3});
    }
    for (re int i=1;i<=k;++i) {
        if (mxid[i]) add[i].push_back(make_pair(mxa[i]-a[i],mxid[i]));
        sort(add[i].begin(),add[i].end(),cmp1);
        ll s=a[i];
        for (auto j:add[i]) {
            mul.push_back((node){j.fi,s,j.se,j.se==mxid[i]?1:2});
            s+=j.fi;
        }
    }
    sort(mul.begin(),mul.end(),cmp2);
    for (auto i:mul) {
        if (ans.size()==m) break;
        if (i.x>0) ans.push_back(make_pair(i.op,i.id));
        else break;
    }
    sort(ans.begin(),ans.end());
    printf("%lu\n",ans.size());
    for (auto i:ans) printf("%d ",i.se); puts("");
    return 0;
}
最后修改:2019 年 10 月 26 日 05 : 30 PM