「CF521D」 Shop

题目说是有三种操作，首先可以知道赋值操作是可以转化为加法操作的，即 \((1,b) \rightarrow (2,b-a_i)\)

然后加法对于一个数你肯定优先选择大的加上去，这样规定了加法顺序之后加法操作也能转变为乘法操作。

然后现在只有乘法操作了，直接从大到小排一遍即可。

值得注意的是，选择了前 \(m\) 大的乘法操作之后，操作顺序需要按照赋值->加法->乘法的顺序进行，若顺序不对显然会使应得的答案变小。

代码：

/*---Author:HenryHuang---*/

/*---Never Settle---*/

#include<bits/stdc++.h>

using namespace std;

const int maxn=5e5+5;

long long mx[maxn],id[maxn];

long long a[maxn],opt[maxn];

vector<pair<int,int> > add[maxn];

vector<pair<long double,int> > mul;

bool cmp(pair<long double,int> a,pair<long double,int> b){

	return opt[a.second]<opt[b.second];

}

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	int k,n,m;cin>>k>>n>>m;

	for(int i=1;i<=k;++i) cin>>a[i];

	for(int i=1;i<=n;++i){

		long long a,b;cin>>opt[i]>>a>>b;

		if(opt[i]==1){

			if(mx[a]<b) mx[a]=max(mx[a],b),id[a]=i;

		}

		if(opt[i]==2){

			add[a].emplace_back(b,i);

		}

		if(opt[i]==3){

			mul.emplace_back(b,i);

		}

	}

	for(int i=1;i<=k;++i) if(mx[i]>a[i]) add[i].emplace_back(mx[i]-a[i],id[i]);

	for(int i=1;i<=k;++i){

		sort(add[i].begin(),add[i].end());

		reverse(add[i].begin(),add[i].end());

		for(auto x:add[i]){

			int u,v;tie(u,v)=x;

			mul.emplace_back(1.0*(a[i]+u)/a[i],v);

			a[i]+=u;

		}

	}

	int cnt=min(m,(int)mul.size());

	cout<<cnt<<'\n';

	sort(mul.begin(),mul.end());

	reverse(mul.begin(),mul.end());

	sort(mul.begin(),mul.begin()+cnt,cmp);

	int num=0;

	if(cnt==0) return 0;

	for(auto x:mul){

		cout<<x.second<<' ';

		++num;

		if(num==cnt) break;

	}

	return 0;

}

巴特西

「CF521D」 Shop

「CF521D」 Shop

最新文章

热门文章