[CF521D] Shop

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;
}