P1109 学生分组题解

樱雪喵 · 2020-01-21 16:03:34 · 题解

蒟蒻的第三篇题解，个人认为讲得比较清楚，求赞QwQ~~

废话少说，直接进入正题：

读完题目，我们就应该知道：输出有两种情况，交换次数和 -1.

先考虑输出 -1 （即不能满足题目条件）的情况：

此时有两种可能，总人数（all）大于组数（n）乘上界（r）或小于组数乘下界（l）。代码实现很简单，求出总数再比较,满足条件输出 -1 。

代码如下：

for(int i=1;i<=n;i++)
{
    all+=a[i];
}
if(all<n*l||all>n*r)
{
    cout<<"-1";
    return 0;
}

然后是满足条件的情况：

用 b 数组存不足下限的组一共缺少的人数，用 c 数组存超过上限的组一共超过的人数。

最简单的方法就是用 c 数组中多出的人数去补 b 数组中缺少的人数，但如果 b,c 不相等呢？

当然要使 b,c 都等于0，所以最少交换次数就是 b,c 中较大的数！这道题就做完了！

上代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[51],b,c,all,l,r,ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    cin>>l>>r;
    for(int i=1;i<=n;i++)
    {
        all+=a[i];
    }
    if(all<n*l||all>n*r)
    {
        cout<<"-1";
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]<l)
        {
            b+=(l-a[i]);
        }
        if(a[i]>r) c+=(a[i]-r);
    }
    cout<<max(b,c);
    return 0;
}

~~大佬勿喷qwq~~

P1109 学生分组 题解

P1109 学生分组题解