P7791 [COCI2014-2015#7] TETA 题解

信息向阳花木 · 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;
}