自动搬运

查看原文

来自洛谷，原作者为

	信息向阳花木 Away From OI

搬运于2025-08-24 22:33:07，当前版本为作者最后更新于2021-08-24 16:57:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题，比较水

题目传送门

好了，分享思路的时候到了：

• 读入时，我们看看这份菜品在不在套餐当中，若在，用桶 $a$ 记录下这份菜品所需的数量；若不在，将这份菜品的单价加到 $ans$ 当中。

• 当数据全部读入完毕时，先用 while 循环循环 $t$ 个我想要的菜品，再用 $i$ 把 $n$ 个菜品遍历一遍，当 a[i]!=0 时，我们计算：

  （1）将第 $i$ 个物品的单价加进单价和变量 $cnt$ 中。

  （2）将 $a_i$ 减 1，代表这个菜品中的一份我已经处理过了。

  （3）计算购买其套餐需要多少钱。

  （4）取两个中的最小值，加进答案中。

为什么可以这样做，这样做的依据是什么？

1. a[i]!=0 时，当且仅当这个菜品出现在套餐当中。

2. 由于每次 $a_i$ 只减 1，所以，不会出现套餐中重复出现 某一菜品，也就是不会有多个同种菜品被算成 1 个菜品出现在套餐当中了。

3. 这样每次到最后（依然在 while 内部）才加上套餐和单价和的最小值，不会把套餐的价格在每个菜品头上都再加一遍。

还不会，就看程序吧。注释都在程序里哦！

C++ 代码

#include <iostream>//尽量缩短代码。 
using namespace std;
int k,x,t,ans,c[20],p[5],s[20],a[20];//意思与题目和解析里的意思相同。
int main(){
	cin>>k;
	for(int i=1;i<=k;i++)cin>>c[i]; 
	cin>>x;
	for(int i=1;i<=4;i++)cin>>p[i];
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>s[i];
		if(s[i]==p[1]||s[i]==p[2]||s[i]==p[3]||s[i]==p[4]){//若是套餐里的菜品。 
			a[s[i]]++;//桶计数。 
		}
		else ans+=c[s[i]];
	}
	while(t--){
		int cnt=0;
		for(int i=1;i<=k;i++){//用 i 循环遍历 n。 
			if(a[i]>0){
				cnt+=c[i];a[i]--;}}
		ans+=min(cnt,x);
	}
	cout<<ans;
	return 0;
}