当前位置:首页 > 题解目录 > 正文内容

学生分组

亿万年的星光5年前 (2021-01-28)题解目录8039

【题目描述】

有N组学生,给出初始时每组中的学生个数,再给出每组学生人数的上界R和下界L(LR),每次你可以在某组中选出一个学生把他安排到另外一组中,问最少要多少次才可以使N组学生的人数都在[L,R]中。

【输入描述】

第一行一个整数N,表示学生组数; n≤50

第二行N个整数,表示每组的学生个数;

第三行两个整数L,R表示下界和上界。

【输出描述】

一个数,表示最少的交换次数,如果不能满足题目条件输出

【样例输入】

2
10 20
10 15

【样例输出】

5

【分析】

1.首先可以考虑“-1”的情况,已知下届L和上届R,如果有n组人,那么人数的下限是n*L,上限是n*R,所有小于下限和大于上限的情况都不符合要求。

2.其次就是考虑最少要交换次数。把每组人数与上下界做比较,求出差值,取差值较大的那个。(因为考虑最少交换次数,目的在于交换成功,取最多的那次)

举例如下:
假设有5组数据分别是10 15 20 25 30

下限是18,上限是23

对于第一组数据10,需要调来18-10=8个

对于第二组数据15,需要调来18-15=3个

对于第三组数据20,数据在范围之内,不需要额外补或者减

对于第四组数据25,需要调走25-23=2个

对于第五组数据30,需要调走30-23=7个

那么一共需要调来11个,需要调走9个。把调走的全部给调来的,还差2个,也就是说这里要以数字最大的为准。

#include<bits/stdc++.h>
using namespace std;
int s[55]; //学生数组
int  n,l,r,sum,sum_l,sum_r;//定义学生组数,下届,上届,学生总人数
int main()
{
    cin>>n; //读入学生组数
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
       sum+=s[i]; //算出总人数    
    }
    cin>>l>>r; // 读入下届和上届;
    if(sum>n*r || sum<n*l) //总人数小于下限或者大于上限表示不符合条件
    {
        cout<<"-1"<<endl;
        return 0;
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            if(s[i]>r)
                sum_r += s[i]-r; //找到多少人需要调走
           if(s[i]<l)
               sum_l += l-s[i]; //找到有多少人需要调来
        }  
    }
     
    cout<<max(sum_l,sum_r); //输出较大的,即最少的次数
    return 0;
}


    扫描二维码推送至手机访问。

    版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

    分享给朋友:
    返回列表

    上一篇:生日

    下一篇:2的幂次方表示

    相关文章

    【题解】黑白棋子移动

    【题目描述】有2n个棋子(n≥4)排成一行,开始位置为白子全部在左边,黑子全部在右边,如下图为n=5的情形:○○○○○●●●●●移动棋子的规则是:每次必须同时移动相邻的两个棋子,颜色不限,可以左移也可...

    【题解】统计自然数

    【题目描述】某次科研调查时得到了n个自然数,每个数均不超过1500000000(1.5*109)。已知不相同的数不超过10000个,现在需要统计这些自然数各自出现的次数,并按照自然数从小到大的顺序输出...

    2021年市北区程序设计竞赛题(⼩学组)

    最⼤值的相乘(maxx.cpp)【问题描述】第⼀⾏有x个正整数a1,a2,..,ax,第⼆⾏有y个正整数b1,b2,...,by,第三⾏有z个正整数c1,c2,...,cz,假设第⼀⾏的x个正整数中的...

    【题解】光荣的梦想

    【题目描述】Prince对他在这片大陆上维护的秩序感到满意,于是决定启程离开艾泽拉斯。在他动身之前,Prince决定赋予King_Bette最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代,平...

    【题解】BFS—迷宫问题(1)

    【题解】BFS—迷宫问题(1)

    【题目描述】一个5*5的矩阵,矩阵内用0,1显示。其中,0是路,表示这个点可以走,1是墙表示这个点不可以走。问,从给定的矩阵中从左上角到右下角最少需要走多少步?注:题目保证有解(不存在左上角和右下角为...

    【题解】航空母舰

    3.航空母舰(aircraft.cpp)【题目描述】航空母舰(Aircraft Carrier),是一种以舰载机为主要作战武器的大型水面舰艇。依靠航空母舰,一个国家可以在远离其国土的地方、不依靠当地机...