L1-095 分寝室坑点吐槽篇（很详细） C++

怼烎@ 2024-05-04 08:13 64阅读 0赞

学校新建了宿舍楼，共有 n 间寝室。等待分配的学生中，有女生 n0 位、男生 n1 位。所有待分配的学生都必须分到一间寝室。所有的寝室都要分出去，最后不能有寝室留空。  
现请你写程序完成寝室的自动分配。分配规则如下：

*  男女生不能混住；
 *  不允许单人住一间寝室；
 *  对每种性别的学生，每间寝室入住的人数都必须相同；例如不能出现一部分寝室住 2 位女生，一部分寝室住 3 位女生的情况。但女生寝室都是 2 人一间，男生寝室都是 3 人一间，则是允许的；
 *  在有多种分配方案满足前面三项要求的情况下，要求两种性别每间寝室入住的人数差最小。

#### 输入格式： ####

输入在一行中给出 3 个正整数 n0、n1、n，分别对应女生人数、男生人数、寝室数。数字间以空格分隔，均不超过 105。

#### 输出格式： ####

在一行中顺序输出女生和男生被分配的寝室数量，其间以 1 个空格分隔。行首尾不得有多余空格。  
如果有解，题目保证解是唯一的。如果无解，则在一行中输出 `No Solution`。

#### 输入样例 1： ####

24 60 10

#### 输出样例 1： ####

4 6

**注意：**输出的方案对应女生都是 24/4=6 人间、男生都是 60/6=10 人间，人数差为 4。满足前三项要求的分配方案还有两种，即女生 6 间（都是 4 人间）、男生 4 间（都是 15 人间）；或女生 8 间（都是 3 人间）、男生 2 间（都是 30 人间）。但因为人数差都大于 4 而不被采用。

#### 输入样例 2： ####

29 30 10

#### 输出样例 2： ####

No Solution

#### **吐槽** ####

作为L1的压轴题之一，坑死你不偿命，谈谈拿满分需要注意那些细节点

细节点一：**三个数都是正整数**，当 n0=1 或 n1=1 时，无解；

细节点二：不允许单人住一间 ==> 在求可分配房间数的时候，可能意识不到，比如，

n0=4、 n1=4、 n=6 ,应该是无解的

细节点三：同性别所有人住一间的情况是允许的：例如

n0=29、 n1=29、 n=2 ,答案应该是：1 1

思路：

1、求n0个女生可以分配的所有房间数x（也就是求能被n0整除的数，然后剔除所有大于等于n的数和等于n0的那一个数（单人单间的情况））

2、同理，求n1可分配的所有房间数y；

3、用双层循环，记录下所有 两边的房间数之和刚好等于n时（既xi+yi=n）的人数差，然后选出人数差最小的那一组即可。

#include<iostream>
    #include<math.h>
    #include<vector>
    #include<limits.h>
    using namespace std;
    
    int main(){
        int n0,n1,n;
        cin>>n0>>n1>>n;
        vector<int> n0_ys, n1_ys;
        int n0_len=sqrt(n0), n1_len=sqrt(n1); 
        for(int i=1; i<=n0_len; i++){ // 符合要求的女生寝室数
            if(i>n)break;
            if(n0%i == 0){
                n0_ys.push_back(i);
                if(n0/i<n && n0/i<n0)n0_ys.push_back(n0/i);
            }
        }
        if(!n0_ys.empty() && n0==n0_len*n0_len)n0_ys.pop_back();
        
            for(int i=1; i<=n1_len; i++){ // 符合要求的男生寝室数
                if(i>n)break;
                if(n1%i == 0){
                    n1_ys.push_back(i);
                    if(n1/i<n && n1/i<n1)n1_ys.push_back(n1/i);
                }
            }
            if(!n1_ys.empty() && n1_len*n1_len == n1)n1_ys.pop_back();
    
    
      //    for(auto e: n0_ys) cout<<e<<" ";
      //    cout<<"\n";
      //    for(auto e: n1_ys)cout<<e<<" ";
      //    cout<<"\n";
    
    
            int min_cha = INT_MAX, idx, idy;
            for(int i=0; i<n0_ys.size(); i++){
                for(int j=0; j<n1_ys.size(); j++){
                    if(n0_ys[i]+n1_ys[j] == n){
                        int x = abs(n0/n0_ys[i] - n1/n1_ys[j]);
        //                    printf("女生%d间：%d人/间，男生%d间：%d人/间，差：%d\n",n0_ys[i],n0/n0_ys[i],n1_ys[j],n1/n1_ys[j],x);
                        if(x<min_cha){
                            min_cha = x;
                            idx = i;
                            idy = j;
                        }
                    }
                }
            }
            if(min_cha < INT_MAX)
                cout<<n0_ys[idx]<<" "<<n1_ys[idy]<<"\n";
            else
                cout<<"No Solution"<<"\n";
            return 0;
        // }
    
    }