当前位置： 首页 > article >正文

PAT甲级 1080 Graduate Admission（30）

article 2024/11/22 5:36:01

文章目录

  • 题目
  • 题目大意
  • 基本思路
  • AC代码
  • 总结

题目

原题链接

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

题目大意

每个申请人都必须提供两个成绩：全国入学考试成绩GE和面试成绩GI，申请人的最终成绩是 (GE+GI) / 2。

录取规则：

  • 申请者将根据其最终成绩由高到低进行排名，并且将从排名列表的顶部开始逐一录取。
  • 如果申请者的最终成绩并列，则按照 GE 成绩由高到低进行排名，如果成绩仍然并列，则并列者的排名必须相同。
  • 每个申请人可以填报 K 个志愿，并且将根据他/她的志愿进行录取：如果按照排名列表，轮到某位学生被录取了，并且其第一志愿学校还未招满人，则他成功被该学校录取。如果名额已满，则按顺序考虑其他志愿，直至成功被录取为止。如果所有报名学校都无法录取该名学生，则该名学生录取失败。
  • 如果出现并列排名，并且并列申请人正在申请同一所学校，那么该学校不得只录取其中一部分申请人，即使超过招生限额，也必须全部录取。

输入格式
第一行包含三个整数，N 表示总申请人数量，M 表示学校数量，K 表示可填报志愿数量。
第二行包含 M 个整数，表示每所学校的计划招生人数。
接下来 N 行，每行包含 2+K 个整数，前两个整数表示一名申请人的GE和GI，接下来K个整数，表示该申请人的志愿学校编号。
所有学校编号 0∼M−1，所有申请人编号 0∼N−1。

输出格式
输出所有研究生院的录取结果。
每所学校的录取结果占据一行，其中包含所有学校录取的申请人的编号。编号必须按升序排列，并用空格分隔。
每行的末尾必须没有多余的空格。
如果某学校没有录取任何学生，则必须相应地输出空白行。

数据范围
1≤N≤40000，1≤M≤100，1≤K≤5，0≤GE,GI≤100，每所学校的计划招生人数不会超过 2000。

基本思路

首先创建一个申请人结点结构Node，里面存储了申请人的志愿学校编号（使用vector来存储），入学考试成绩ge，面试成绩gi，总成绩score，申请人的编号val。再创建一个结构体数组node，存储每个申请人的结点。

struct Node {
    vector<int> vc;// 存储每个学生的志愿学校编号
    int ge;// 入学考试成绩
    int gi;// 面试成绩
    double score;// 总成绩
    int val;// 每个学生的编号
}node[N]

用vector存储每所学校的录取人数和每所学校录取学生的编号

vector<int> a(m);// 存储每所学校的录取人数
vector<vector<int>> c(m);// 存储每所学校录取学生的编号

输入完数据后，对结构体数组node进行排序：根据申请人的总分和考试分数 GE 对申请人列表node进行排序，总分越高的排在前面，当总分相等时按照 GE 来排序，GE 越高排在越前面。

排序规则：

// 注意这里必须要加引用，因为数据很大，每次排序都需要调用比较函数cmp
//不加引用会产生大量拷贝，时间效率大大降低
bool cmp(const Node& a, const Node& b)
{
    if (a.score == b.score)
    {
        return a.ge > b.ge;
    }
    return a.score > b.score;
}

排序：

sort(node, node + n, cmp);

接下来遍历申请人列表node，对每个申请人的志愿学校进行遍历。对于每个志愿学校，检查该学校的录取名额是否为0。如果申请人在符合录取规则的前提下，所有志愿学校都录满了，则表示录取失败。

如果不为0则将该申请人的编号加入该志愿学校的录取学生列表且该学校的录取名额减一，并跳出内层循环，继续遍历下一个申请人。

如果为0则获取该学校录取的最后一名学生的编号，再与他的总成绩score和考试成绩ge进行对比，如果两者都相等，也将该申请人加入该志愿学校的录取学生列表，并跳出内层循环；如果不相等则继续遍历该申请人的志愿学校列表。

那么问题来了，因为结构体数组node已经排序过了（排序前的结构体数组下标等于每个申请人的编号，排序后就不相等了），所以不能通过结构体数组下标去访问对应的申请人。

如何解决这个问题？——>在排序前，再创建一个与node一模一样的结构体数组nodecopy，不对它进行排序，这样就可以通过结构体数组下标去访问对应的申请人结构体。

可以在输入结构体数组的时候每创建了一个新的结构体，则再拷贝复制一模一样的新结构体出来。

for (int i = 0; i < n; i++)
{
    cin >> node[i].ge >> node[i].gi;
    node[i].val = i;
    node[i].score = double(node[i].ge + node[i].gi) / 2;
    int K = k;
    while (K--)
    {
        int x;
        cin >> x;
        node[i].vc.push_back(x);
    }
    nodecopy[i]=node[i];//复制一模一样的结构体数组
}

以下是分配录取结果的过程：

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < node[i].vc.size(); j++)
    {
        int l = node[i].vc[j];
        if (a[l] > 0)
        {
            c[l].push_back(node[i].val);
            a[l] -= 1;
            break;
        }
        else{
            int t=c[l].back();
            if(node[i].score==nodecopy[t].score&&node[i].ge==nodecopy[t].ge)
            {
                c[l].push_back(node[i].val);
                break;
            }
        }
    }
}

最后再打印每个学校的录取结果，注意：录取结果要求升序，所以每次打印一个学校的录取结果时需要再排序

for (int i = 0; i < m; i++)
{
    if (c[i].size() > 0)
    {
        sort(c[i].begin(), c[i].end());// 需要对录取结果再进行排序
        for (int j = 0; j < c[i].size(); j++)
        {
            if (j != (c[i].size() - 1))
            {
                cout << c[i][j] << " ";
            }
            else {
                cout << c[i][j];
            }
        }
    }
    cout << endl;
}

AC代码

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 4e4 + 10;
int n, m, k;
struct Node {
    vector<int> vc;// 存储每个学生的志愿学校编号
    int ge;// 入学考试成绩
    int gi;// 面试成绩
    double score;// 总成绩
    int val;// 每个学生的编号
}node[N],nodecopy[N];

// 注意这里必须要加引用，因为数据很大，每次排序都需要调用比较函数cmp
//不加引用会产生大量拷贝，时间效率大大降低
bool cmp(const Node& a, const Node& b)
{
    if (a.score == b.score)
    {
        return a.ge > b.ge;
    }
    return a.score > b.score;
}
int main()
{
    //加速
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m >> k;
    vector<int> a(m);// 存储每所学校的录取人数
    vector<vector<int>> c(m);// 存储每所学校录取学生的编号
    for (int i = 0; i < m; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> node[i].ge >> node[i].gi;
        node[i].val = i;
        node[i].score = double(node[i].ge + node[i].gi) / 2;
        int K = k;
        while (K--)
        {
            int x;
            cin >> x;
            node[i].vc.push_back(x);
        }
        nodecopy[i]=node[i];//复制一模一样的结构体数组
    }
    sort(node, node + n, cmp);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < node[i].vc.size(); j++)
        {
            int l = node[i].vc[j];
            if (a[l] > 0)
            {
                c[l].push_back(node[i].val);
                a[l] -= 1;
                break;
            }
            else{
                int t=c[l].back();
                if(node[i].score==nodecopy[t].score&&node[i].ge==nodecopy[t].ge)
                {
                    c[l].push_back(node[i].val);
                    break;
                }
            }
        }
    }
    for (int i = 0; i < m; i++)
    {
        if (c[i].size() > 0)
        {
            sort(c[i].begin(), c[i].end());// 需要对录取结果再进行排序
            for (int j = 0; j < c[i].size(); j++)
            {
                if (j != (c[i].size() - 1))
                {
                    cout << c[i][j] << " ";
                }
                else {
                    cout << c[i][j];
                }
            }
        }
        cout << endl;
    }
    return 0;
}

在PAT和AcWing平台都通过了全部样例
在这里插入图片描述
在这里插入图片描述

注意：排序函数要用 & 引用传参，不然会超时

改进：因为分数 score = ge + gi 不会超出 int 范围, score / 2 和 score 排名效果一样， 不除2不会影响结果，而且还可以巧妙躲避除2后double不能精确表示的问题。

本人还写出来了一个优先队列版本，在PAT平台可以过，但是在AcWing平台却超时了，应该是数据量太大了况且这个版本的时间复杂度确实比较高。所以不推荐使用这种版本。

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N = 4e4 + 10;
int n, m, k;
struct Node {
    vector<int> vc;
    int ge;
    int gi;
    double score;
    int val;
}node[N];
struct cmp {
    bool operator()(const Node& a, const Node& b)
    {
        if (a.score == b.score)
        {
            return a.ge < b.ge;
        }
        return a.score < b.score;
    }
};
int main()
{
    //加速
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m >> k;
    vector<int> a(m);
    vector<vector<int>> c(m);
    priority_queue<Node, vector<Node>, cmp> q;//优先队列
    for (int i = 0; i < m; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> node[i].ge >> node[i].gi;
        node[i].val = i;
        node[i].score = double(node[i].ge + node[i].gi) / 2;
        int K = k;
        while (K--)
        {
            int x;
            cin >> x;
            node[i].vc.push_back(x);
        }
        q.push(node[i]);
    }
    while (!q.empty())
    {
        auto t = q.top();
        q.pop();
        bool vis = false;
        int l;
        for (int i = 0; i < t.vc.size(); i++)
        {
            l = t.vc[i];
            if (a[l] > 0)
            {
                a[l] -= 1;
                c[l].push_back(t.val);
                vis = true;
                break;
            }
        }
        if (vis)
        {
            //寻找有没有相同分数的学生
            vector<Node> v;
            while (!q.empty())
            {
                auto tt = q.top();
                bool viss=false;
                if (tt.score == t.score && tt.ge == t.ge)
                {
                    for (int i = 0; i < tt.vc.size(); i++)
                    {
                        int r = tt.vc[i];
                        if (r == l)
                        {
                            viss=true;
                            c[l].push_back(tt.val);//分数和志愿相同则入队
                            if (a[l] > 0)
                            {
                                a[l] -= 1;
                            }
                            q.pop();
                            break;
                        }
                        else {
                            if (a[r] > 0)
                            {
                                //分数相同但志愿不同，志愿学校有名额，存储在v容器里
                                viss=true;
                                v.push_back(tt);
                                q.pop();
                                break;
                            }
                        }
                    }
                    if(viss==false)
                    {
                        //分数相同但志愿不同，志愿学校都招满了，则该同学录取失败，出队即可
                        q.pop();
                    }
                }
                else {
                    //如果没有分数相同的，则退出循环
                    break;
                }
            }
            if (v.size() > 0)//将同分数但不同志愿的学生重新入队
            {
                for (int i = 0; i < v.size(); i++)
                {
                    q.push(v[i]);
                }
            }
        }
    }
    //打印录取结果
    for (int i = 0; i < m; i++)
    {
        if (c[i].size() > 0)
        {
            sort(c[i].begin(), c[i].end());
            for (int j = 0; j < c[i].size(); j++)
            {
                if (j != (c[i].size() - 1))
                {
                    cout << c[i][j] << " ";
                }
                else {
                    cout << c[i][j];
                }
            }
        }
        cout << endl;
    }
    return 0;
}

在PAT平台可以通过
在这里插入图片描述
在AcWing平台超时了，因为数据量太大了，很容易超时，所以还是不推荐优先队列这种写法。
在这里插入图片描述

可以参照一下柳神的思路和写法：传送门

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct peo{
    int id, ge, gi, fin;
    vector<int> choice;
};
bool cmp(peo& a, peo& b) {
    if (a.fin != b.fin) return a.fin > b.fin;
    return a.ge > b.ge;
}
bool cmp2(peo& a, peo& b) {
    return a.id < b.id;
}
int main(){
    int n, m, k, quota[110], cnt[110] = {0};
    scanf("%d%d%d", &n, &m, &k);
    vector<peo> stu(n), sch[110];
    for(int i = 0; i < m; i++)
        scanf("%d",&quota[i]);
    for(int i = 0; i < n; i++) {
        scanf("%d%d", &stu[i].ge, &stu[i].gi);
        stu[i].id = i;
        stu[i].fin = stu[i].ge + stu[i].gi;
        stu[i].choice.resize(k);
        for(int j = 0; j < k; j++)
            scanf("%d", &stu[i].choice[j]);
    }
    sort(stu.begin(), stu.end(), cmp);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < k; j++) {
            int schid = stu[i].choice[j];
            int lastindex = cnt[schid] - 1;
            if(cnt[schid] < quota[schid] || (stu[i].fin == sch[schid][lastindex].fin) && stu[i].ge == sch[schid][lastindex].ge) {
                sch[schid].push_back(stu[i]);
                cnt[schid]++;
                break;
            }
        }
    }
    for(int i = 0; i < m; i++) {
        sort(sch[i].begin(), sch[i].end(), cmp2);
        for(int j = 0; j < cnt[i]; j++) {
            if(j != 0) printf(" ");
            printf("%d", sch[i][j].id);
        }
        printf("\n");
    }
    return 0;
}

在这里插入图片描述
在这里插入图片描述

总结

这道题的题目很长而且生词也比较多，比如 Graduate Admission：研究生入学，exceeded：超出，quota：定额,限额，unfortunate：不幸的，correspondingly：相应的，相对地

这需要做题人有一定的英语阅读和翻译能力，这道题不算很难，但是要把题目完完整整翻译一遍确实需要花挺长时间。所以，1. 平时要多记一下单词，如果看不懂再结合上下文去猜测它的意思，还需要非常的有耐心。2. 多刷题，保持做题的手感和提升Debug的能力。


http://www.kler.cn/a/403902.html

相关文章：

  • 使用node-addon-api实现从c到nodejs模块全流程
  • Ubuntu20.04从零安装IsaacSim/IsaacLab
  • 手机领夹麦克风哪个牌子好，哪种领夹麦性价比高，热门麦克风推荐
  • 大数据调度组件之Apache DolphinScheduler
  • 【gitlab】部署
  • 测评部署和管理 WordPress 最方便的面板
  • 计算机网络-Python通信
  • 什么是Git，有什么特点
  • 51c自动驾驶~合集30
  • 【AI日记】24.11.19 GraphRAG
  • Python爬虫项目 | 二、每日天气预报
  • git上传文件到远程仓库
  • 【东莞石碣】戴尔R740服务器维修raid硬盘问题
  • KubeSphere 最佳实战：K8s 构建高可用、高性能 Redis 集群实战指南
  • Jenkins的环境部署
  • Linux常用命令之wc命令详解
  • PointNet++项目分析
  • JAVA篇之类和对象
  • 使用 LSTM（长短期记忆网络） 模型对时间序列数据（航空旅客人数数据集）进行预测
  • vue2.0新建项目
  • 无人机侦察打击方案（3）
  • 亚马逊云服务器（AWS）：功能、优势与使用指南
  • 【YOLOv8】安卓端部署-1-项目介绍
  • 【C++】数据上传的方式。持久化的方式。通过 JSON，序列化与反序列化。
  • Vue2 Class Component 使用指南：提升组件开发的可维护性
  • 嵌入式linux中QT信号与槽基本操作与实现