AT_arc174_b [ARC174B] Bought Review 题解

题目翻译

针对 \(T\) 个测试用例解决以下问题：

在美食评论网站 EatCocoder 上，你可以评论餐厅的星级(从 \(1\) 到 \(5\) 的整数)。

最初，由厨师长 \(B\) 管理的餐厅有 \(A_i\) 条 \(i\) 星级评价。（ \(1 ≤ i ≤ 5\) ）

厨师可以向 EatCocoder 管理部门 行贿 提供 \(P_i\) 日元，以获得一次 额外 的 \(i\) 星评论。（ \(1 ≤ i ≤ 5\) ）

通过贿赂添加总共 \(k\) 条评论后，将有 \(A_1+A_2+A_3+A_4+A_5+k\) 条评论。

厨师 \(B\) 希望这些评论的平均评分至少为三星。

请求出实现这一目标所需的最低 贿赂 消费总额。

算法

法一（暴力）

不会写暴力了，呜呜呜…

法二（正解）

首先，如果平均分就 \(≥3\) ，显然答案为 \(0\) 。

然后—我们可以发现一个 人类智慧 优化：

我们每增加一条评论，那么应新增的星数就加 \(3\) ，
那么为了补回星数，我们只能选择比 \(3\) 大的，即 \(4\) 和 \(5\) 。

我们可以贪心：

• 全买 \(4\) 分的
• 买 \(1\) 个 \(4\) 分的和一些 \(5\) 分的
• 全买 \(5\) 分的

#include<bits/stdc++.h>
#define int long long
#define fd(i,a,b) for(int i=a;i<=b;i=-~i)
using namespace std;
int n,c,T,a[300100],f[2500],p[300100],ans=-1,cnt,sum;
signed main()
{
	ios::sync_with_stdio(0);
	cin>>T;
	while(T--)
	{
   		cnt=sum=0;
   		ans=1e18;
		fd(i,1,5) cin>>a[i],cnt+=a[i]*3,sum+=a[i]*i;
		fd(i,1,5) cin>>p[i];
		if(sum>=cnt)//平均分≥3
		{
			cout<<0<<endl;
			continue;
		}
		if((cnt-sum)%2)
		ans=min(ans,min(((cnt-sum)/2+1)*p[5],((cnt-sum)/2)*p[5]+p[4]));
		//买1个4分的和一些5分的/全买5分的
		if((cnt-sum)%2==0)
		ans=min(ans,((cnt-sum)/2)*p[5]);
		//全买5分的
		ans=min(ans,(cnt-sum)*p[4]);
		//全买4分的
		cout<<ans<<endl;
	}
	return 0;
}

无关的话（审核大大，求过审）：被禁言了，怎么解啊？

感谢观看！