学生分组
【题目描述】
有N组学生,给出初始时每组中的学生个数,再给出每组学生人数的上界R和下界L(L≤R),每次你可以在某组中选出一个学生把他安排到另外一组中,问最少要多少次才可以使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个,也就是说这里要以数字最大的为准。
扫描二维码推送至手机访问。
版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。