[题解]关于平衡膳食易错解法的讨论

先贴上错误代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int v[4]={};
        for(int i=0;i<4;i++)//读入数据
            cin>>v[i];
        bool flag=true;//用于判断是否还有三种不同类型的
        int ans=0;
        while(flag)
        {
            int cnt=0;//记录减少的数
            for(int i=0;i<4;i++)//读入数据
                if(v[i]>0&&cnt<3)v[i]--,cnt++;//将食物份数--，将记录数++
            if(cnt!=3)flag=false;//若不足三份食物则退出循环
            else ans++;//若达到3次则增加人数
        }
        cout<<ans<<endl;
    }
    return 0;
}

分析：

*此解法为错误解法

* 在2 3 3 4时，输出3，正确答案为4，第一次1 2 3 3 第二次 1 2 2 2 第三次 1 1 1 1第四次0 0 0 1

* 而本解为第一次1 2 2 4 第二次0 1 1 4第三次 0 0 0 3，第四份食物没有充分利用

* 由于取用食物的随机性，此解法可能会将少的先取完，而不用到最多的那份，导致多的用不上

* 而事实上我们应该尽量用多份数的食物，应该用到排序

* 解法一：先将数组排序每次取最多的两个和最少的一个

* 重复上一步直到最少的为0时

* 答案还要加上第二少的食物数

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        vector<int> v;//vector 有点多此一举了，但是契合本章标题
        for(int i=0;i<4;i++)//读入数据
        {
            int a;
            scanf("%d",&a);
            v.push_back(a);
        }
        //每次将数组从小到大排序
        //每次取两个最多的和一个最少的直到最少的为0，那么第二少的就是剩下的份数
        int ans=0;
        sort(v.begin(),v.end());
        while(v[0]--)
        {
            v[2]--;
            v[3]--;
            sort(v.begin(),v.end());
            ans++;
        }
        cout<<ans+v[1]<<endl;
    }
    return 0;
}

* 问题来了：我们为什么不直接每次取最多的三份，再排序，那循环条件应该是什么呢v[1]==0

* 当然可以，但是这种解法实际上多计算了第二少食物数的个数，因此解法一为优

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        vector<int> v;
        for(int i=0;i<4;i++)//读入数据
        {
            int a;
            scanf("%d",&a);
            v.push_back(a);
        }
        //每次将数组从小到大排序
        //每次取两取三个最多的，直到第二少的食物数为0
        int ans=0;
        sort(v.begin(),v.end());
        while(v[1]--)
        {
            v[2]--;
            v[3]--;
            sort(v.begin(),v.end());
            ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}