CF512D
聪明的想法。
首先对于同一个 i 必定保留最大的赋值操作,并且顺序为赋值-加-乘。
并且我们最终答案是所有元素的乘,那么乘操作对答案作贡献很好写就是乘的值。
那么我们想办法把余下两种操作用乘操作表示。
把大于 \(va_i\) 的赋值操作变成加操作,因为乘之前对于某个 i 一定加的越多越好,所以将加法减序排序即可。
可能会问赋值的加法不是第一个并且要用上怎么办,把顺序调换一下即可,加的值是一样的。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<bitset>
using namespace std;
#define db double
#define ll long long
#define ull unsigned long long
#define ld long double
const int MAXN=1e5+5;
const int INF=0x3f3f3f3f;
void read(int &x){
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){
if(s=='-') f=-1;s=getchar();
}
while(s>='0'&&s<='9'){
x=(x<<3)+(x<<1)+(s^48);s=getchar();
}
x*=f;
}
struct ren{
int id;db x;
ren(){};
ren(int I,db X){id=I;x=X;}
}a[MAXN];
int n,k,m,fz[MAXN],fk[MAXN];
vector<ren> v,v1[MAXN];
db va[MAXN];
bool c0(ren x,ren y){return x.x>y.x;}
bool c1(ren x,ren y){return fk[x.id]<fk[y.id];}
int main(){
read(k);read(n);read(m);
a[0].id=0;a[0].x=0;
for(int i=1;i<=k;i++) scanf("%lf",&va[i]);
for(int i=1,x;i<=n;i++){
scanf("%d%d%lf",&a[i].id,&x,&a[i].x);
if(a[i].id==1){
a[i].id=i;if(a[i].x>a[fz[x]].x) fz[x]=i;fk[i]=1;continue;
}
if(a[i].id==2){
a[i].id=i;v1[x].push_back(a[i]);fk[i]=2;continue;
}
a[i].id=i;v.push_back(a[i]);fk[i]=3;
}
for(int i=1;i<=k;i++){
if(fz[i]&&a[fz[i]].x>va[i]){
v1[i].push_back((ren){a[fz[i]].id,a[fz[i]].x-va[i]});
}
sort(v1[i].begin(),v1[i].end(),c0);
db tmp=va[i];
for(auto u:v1[i]){
v.push_back((ren){u.id,(tmp+u.x)/tmp});
tmp+=u.x;
}
}
sort(v.begin(),v.end(),c0);
vector<ren> oo;
for(int i=0;i<min(m,(int)v.size());i++) oo.push_back(v[i]);
sort(oo.begin(),oo.end(),c1);
printf("%d\n",(int)oo.size());
for(auto u:oo) printf("%d ",u.id);
return 0;
}