题目大意：给定k个数，n个操作，每个操作有三种类型：
1.a[i]=b
2.a[i]+=b
3.a[i]*=b
其中i和b是操作指定的
现在你可以进行最多m次操作，每个操作最多进行一次，要求操作结束后所有数的乘积最大
按使用的顺序输出每个操作的编号
乱七八糟地写了一发D……结果最后没调出来QAQ B题也没写 到最后就写了A和C 排了100+。。。
首先对于同一个数我们执行的所有操作一定是按照1-2-3的顺序
操作1最多执行1次 因此我们不妨将每个数的操作1取最大后当做操作2处理
现在就只剩下了两个操作 2和3
3操作的影响是答案*=b
2操作的影响是答案*=(a[i]+b)/a[i]
但是a[i]是会变化的，，因此不能直接贪心
我们发现2操作虽然彼此独立 但是在操作数为m的限制下 显然对于每个数 2操作的顺序按照从大大小取是更优的
因此我们不妨将每个数所有的2操作都排个序，将最大的加入堆
然后每次取出堆顶 如果这个堆顶是操作2 就取出这个数的下一个操作2并计算本次的(a[i]+b)/a[i]
最后将所有操作按照type排个序即可
时间复杂度O(mlogn)
注意a[i]可能会加爆
#include <queue>#include <cmath>#include <vector>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 100100#define EPS 1e-9using namespace std;int k,n,m;int a[M],to_modify[M];long long _a[M];struct abcd{int type,i,b;}b[M];vector<pair<double,int> > modifictions[M];priority_queue<pair<double,int> > heap;int stack[M],top;bool Compare(int x,int y){return b[x].type < b[y].type;}int main(){//freopen("fuck.txt","r",stdin);int i;cin>>k>>n>>m;for(i=1;i<=k;i++)scanf("%d",&a[i]),_a[i]=a[i];for(i=1;i<=n;i++){scanf("%d%d%d",&b[i].type,&b[i].i,&b[i].b);if(b[i].type==1){if(!to_modify[b[i].i]||b[to_modify[b[i].i]].b<b[i].b)to_modify[b[i].i]=i;}else if(b[i].type==2)modifictions[b[i].i].push_back(make_pair(b[i].b,i) );elseheap.push( pair<double,int>(log(b[i].b),i) );}for(i=1;i<=k;i++)if(to_modify[i]&&b[to_modify[i]].b>a[i])modifictions[i].push_back(pair<double,int>(b[to_modify[i]].b-a[i],to_modify[i]));for(i=1;i<=k;i++)if(modifictions[i].size()){sort(modifictions[i].begin(),modifictions[i].end());pair<double,int> temp=modifictions[i].back();modifictions[i].pop_back();temp.first=log(a[b[temp.second].i]+temp.first)-log(a[b[temp.second].i]);heap.push(temp);}for(i=1;i<=m&&heap.size();i++){ pair<double,int> temp=heap.top();heap.pop();stack[++top]=temp.second;if( b[temp.second].type==1 )_a[b[temp.second].i]+=b[temp.second].b-a[b[temp.second].i];else if( b[temp.second].type==2 )_a[b[temp.second].i]+=b[temp.second].b;elsecontinue;if(modifictions[b[temp.second].i].size()){pair<double,int> _temp=modifictions[b[temp.second].i].back();modifictions[b[temp.second].i].pop_back();_temp.first=log(_a[b[temp.second].i]+_temp.first)-log(_a[b[temp.second].i]);heap.push(_temp);}}sort(stack+1,stack+top+1,Compare);cout<<top<<endl;for(i=1;i<=top;i++)printf("%d%c",stack[i],i==top?'\n':' ');}
人若软弱就是自己最大的敌人
