题解：P14174 【MX-X23-T4】卡常数

题意简述

定义数列 $a_i$ 的代价 $P_i$ 为其中所有元素的乘积再乘以 $x_i$ ，即 $P_i = x_i \prod_{j=1}^{l_i} a_{i, j} \text{。}$
定义全体数列的总代价 $P$ 为每个数列的代价之和，即 $P = \sum_{i = 1}^{n} P_i \text{。}$

对于所有

P_i

可以修改一共不超过

k

次，让

a_{i, j}

变为

a_{i, j}-b_{i, j}

，最终让

P

最小。

思路分析

考虑贪心，

P

为了最小一定要每一个

P_i

小。首先考虑每一个

P_i

，每一次修改相当于对

P_i

乘上一个真分数

\frac{a_{i,j}-b_{i,j}}{a_{i,j}}

,选真分数最小的一定更优，那么相对于整体的

P

计算修改每一个可以给出的差值贡献，并将这个差值放进大根堆，因为

k

小于等于所有序列加起来的总长，直接取全部前

k

个堆顶就好。

AC CODE

CPP

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
long long a[500005],b[500005];
priority_queue<long long> Q;
pair<long double,int> ans[500005];
long long result;
int main()
{
	int n,k;
	cin>>n>>k;
	while(n--)
	{
		long long x,l;
		cin>>x>>l;
		long long currmul=x;
		for(int i=1;i<=l;i++)
		{
			cin>>a[i];
			currmul*=a[i];
		}
		result+=currmul;
		for(int i=1;i<=l;i++)
		{
			cin>>b[i];
		}
		for(int i=1;i<=l;i++)
		{
			ans[i].first=1.l*(a[i]-b[i])/a[i];
			ans[i].second=i;
		}
		sort(ans+1,ans+l+1);
		for(int i=1;i<=l;i++)
		{
			long long now=currmul;
			now=currmul/a[ans[i].second]*b[ans[i].second];
			//cout<<currmul-now<<" ";
			Q.push(now);
			currmul-=now;
			//cout<<currmul<<endl;;
		}
	}
	for(int i=1;i<=k;i++)
	{
		//cout<<result<<" ";
		result-=Q.top();
		Q.pop();
	}
	cout<<result;
	return 0;
}

题解：P14174 【MX-X23-T4】卡常数

文章操作

题意简述

思路分析

AC CODE

相关推荐

评论

题解：P14174 【MX-X23-T4】卡常数