CF521D Shop(贪心)题解

发布于 2020-12-21  302 次阅读


食用前提示:本文搬自作者的洛谷博客。

题面:

有 $k$ 个整数 $a_1,a_2,\dots,a_k$ , $n$ 个操作,格式为 $opt,i,val$ , $opt$ 是操作类型,可能为1、2、3,分别代表将 $a_i$ 赋值为 $val$ ,将 $a_i$ 加上 $val$ ,将 $a_i$ 乘以 $val$ 。现在要从这 $n$ 个操作里选 $m$ 个,要使$\prod \limits_{i=0}^na_i$最大。

$k,n \le 10^5$,$0 \le m \le n$.

分析:

题外话:看了@ww3113306大佬的题解才想出来的,所以题解可能跟他的有所相似,见谅$QvQ$

一下子考虑3种操作,很难再短时间内想到解法(也可能是我太菜了

我们从简单的开始,如果只有3号操作,那么因为乘法满足结合律,因此答案与每次操作的对象无关。所以我们可以直接按操作的乘法的值排序从大到小取就可以了。

然后考虑把加法变成乘法。同样,我们从大到小进行排序取值。我们可以把任意一个加法看成一个$val$为$\frac{x}{y}$ 的乘法。

然后再看赋值,在前面两点想清楚的情况下赋值也挺好想了:在 $val$ 大于 $a_i$ 大的情况下,我们把它看成 $val$ 为 $val-a_i$ 的加法, $val$ 小于等于 $a_i$ 的情况下肯定是不取的。

上述思路可以用多个$vector$实现。

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010;

int n,m,k,op,sum;
long long x,y;
long long a[N],Rec[N];
pair<long long,int> vec1[N];
vector< pair<long long,int> > vec2[N],vec3;
priority_queue< pair<long double,int> >Q;
vector<int> ans;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline void Print(){        //输出部分 
    for (int i=1;i<=k;i++){
        for (int j=0;j<=Rec[i]-1;j++)
            if (vec2[i][j].second<0) ans.push_back(-vec2[i][j].second);
        for (int j=0;j<=Rec[i]-1;j++)
            if (vec2[i][j].second>0) ans.push_back(vec2[i][j].second);
    }
    while (!vec3.empty()){      //把所有操作转化为乘法后统计答案 
        ans.push_back(vec3.back().second);
        vec3.pop_back();
    }
    printf("%d\n",ans.size());
    for (vector<int>::iterator it=ans.begin();it!=ans.end();it++)
        printf("%d ",*it);
    printf("\n");
}

signed main(){
    //freopen("CF521D.in","r",stdin);
    //freopen("CF521D.out","w",stdout);
    k=read(),n=read(),m=read();
    for (int i=1;i<=k;i++)
        a[i]=read();
    for (int i=1;i<=n;i++){
        op=read(),x=read(),y=read();
        if (op==1) vec1[x]=max(vec1[x],make_pair(y,i));
        if (op==2) vec2[x].push_back(make_pair(y,i));
        if (op==3) vec3.push_back(make_pair(y,i));
        //根据操作的类别放入不同的vector中 
    }
    for (int i=1;i<=k;i++){
        if (vec1[i].first>a[i]) vec2[i].push_back(make_pair(vec1[i].first-a[i],-vec1[i].second));
        //如果赋值操作后的值比原来的大,就把它转化成加法操作
        sort(vec2[i].begin(),vec2[i].end(),greater< pair<long long,int> >());//从大到小排序
        sum+=vec2[i].size();
    }
    sort(vec3.begin(),vec3.end(),greater< pair<long long,int> >());
    while (vec3.size()>m) vec3.pop_back();  //把m之后的较劣操作去掉
    if (sum+vec3.size()<=m){        //加法和乘法加起来不到m,全部选取 
        for (int i=1;i<=k;i++)
            Rec[i]=vec2[i].size();
        Print();
        return 0;
    }
    for (int i=1;i<=k;i++){
        if (Rec[i]<vec2[i].size())
            Q.push(make_pair(1.0L*vec2[i][Rec[i]++].first/a[i],i));
        //把加法转化为乘法 
    }
    for (int i=vec3.size();i<=m-1;i++){
        int x=Q.top().second;
        Q.pop();
        a[x]+=vec2[x][Rec[x]-1].first;
        if (Rec[x]<vec2[x].size())
            Q.push(make_pair(1.0L*vec2[x][Rec[x]++].first/a[x],x));
        //把加法转化为乘法
    }
    while (!vec3.empty()){
        int x=Q.top().second;
        long long val1=vec2[x][Rec[x]-1].first;
        long long val2=vec3.back().first;
        if (val1<=a[x]*(val2-1)) break;
        Q.pop();
        vec3.pop_back(),a[x]+=val1;
        if (Rec[x]<vec2[x].size())
            Q.push(make_pair(1.0L*vec2[x][Rec[x]++].first/a[x],x));
    } 
    while (!Q.empty()){
        int x=Q.top().second;
        Q.pop();
        Rec[x]--;
    }
    Print();
    return 0;
}

我们无法选择过去,但我们可以改变未来。