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

学生分组

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

【题目描述】

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

【输入描述】

第一行一个整数N，表示学生组数； n≤50

第二行N个整数，表示每组的学生个数；

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

【输出描述】

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

【样例输入】

2
10 20
10 15

【样例输出】

【分析】

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; 
}