【Codeforces 521D】Shop | Mrsrz's blog

贪心

题目大意：

给定 $n$ 个数，$m$ 个操作，要求选择不超过 $k$ 个操作并按一定顺序执行。要求使得最后所有数的乘积最大。

求一种操作的方案。

操作有三种：单点赋值，单点加，单点乘。

所有整数非负。

题解：

对某个数，执行操作的顺序显然是赋值、加、乘。

由于我们是要使总乘积最大，所以乘法操作的贡献是一定的，不会因为原数具体是多少而改变。

赋值操作显然最多执行一次，赋值为最大的。

而加法操作，我们显然是从大到小取最优。

考虑把加法操作转化为乘法操作，那么 $a+x$ 可以看做 $a\times \frac{a+x}{a}$。我们把 $\frac{a+x}a$ 看做要乘的数就好了。

考虑赋值操作，可以将其转化为一个加法操作，并和加法一起考虑。

这样做并不会影响顺序，原因：如果赋值操作没被选取则无影响。如果赋值操作被选取，则实际操作时将其放到前面，那么它确实产生了贡献。

然后我们就把所有操作都转化为乘法了。用分数存储每个乘数，排序后取最前面的即可。

时间复杂度 $O(m\log m)$。

Code：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+5;
typedef long long LL;
struct frac{
    LL x,y;
    inline bool operator<(const frac&rhs)const{return (long double)x/y<(long double)rhs.x/rhs.y;}
};
struct data{
    frac f;int id;
    inline bool operator<(const data&rhs)const{return f<rhs.f;}
};
vector<pair<int,int> >add[N];
vector<data>p;
struct opts{
    int tp,x,val;
}g[N];
int n,m,k,cov[N],a[N];
vector<int>ans[4];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=m;++i){
        cin>>g[i].tp>>g[i].x>>g[i].val;
        if(g[i].tp==1){
            if(!cov[g[i].x]||g[cov[g[i].x]].val<g[i].val)cov[g[i].x]=i;
        }else
            if(g[i].tp==2){
                add[g[i].x].push_back(make_pair(g[i].val,i));
            }
            else{
                p.push_back((data){(frac){g[i].val,1},i});
            }
    }
    for(int i=1;i<=n;++i){
        LL x=a[i];
        if(cov[i]&&g[cov[i]].val>x)add[i].push_back(make_pair(g[cov[i]].val-x,cov[i]));
        sort(add[i].rbegin(),add[i].rend());
        for(int j=0;j<add[i].size();++j)
            p.push_back((data){(frac){x+add[i][j].first,x},add[i][j].second}),x+=add[i][j].first;
    }
    sort(p.rbegin(),p.rend());
    for(int i=0;i<k&&i<p.size();++i)
        ans[g[p[i].id].tp].push_back(p[i].id);
    cout<<ans[1].size()+ans[2].size()+ans[3].size()<<'\n';
    for(int x=1;x<=3;++x)
    for(int i=0;i<ans[x].size();++i)cout<<ans[x][i]<<' ';
    return 0;
}