关键词:
更多PAT题解–acking=you.github.io
题目
题目翻译
实际上就和我们高考录取的过程是一样的。
题目是给出了N个考生的两种成绩(初试和复试)。
每个考生填满K个学校志愿。
然后通过成绩的高低(初试和复试的总和)决定录取的先后顺序。
每个学校有相应的名额限制,如果出现两个初试和复试分数都完全一样的人,则名额不存在限制。
最后要我们输出每个学校的录取名单(以0~N-1代号表示学生)。
我的解题思路
- 如何模拟这整个录取过程呢?
- 把输入的数据先存下来。
- 将学生的成绩(总和成绩、初试成绩)和学生编号进行映射。
- 通过映射好的数组自定义排序,把总和成绩好的放前面,如果总和成绩相同,则比较初试成绩。
- 在前面的人,他拥有优先选择权,通过他这个编号找到他对应的志愿表,并从头到尾录取。(录取通过一个
AdmissionList[i]
数组存下编号为 i 的学校的录取情况) - 通过
AdmissionList[i]
数组存下录取情况的过程中,需要判断这个学校是否已经录满了,如果录取满了,则和它的最低分进行比较,如果和它完全相同则继续录取(不可能比它大,因为本就已经排好序进行录取的) - 最后再通过
AdmissionList
打印结果即可。
代码解读
基本的变量
基本变量
int *schoolN; //存储每个学校的限额
int **studentN; //存储每个学生的分数和志愿
vector<tuple<int, int, int>> students_sort; //这个只是用来排序的工具
vector<tuple<int, int, int>> *AdmissionList;//存储每个学校的录取名单
/*其实可以把tuple用自定义的数据结构代替,只是C++11标准自带我就直接拿这个过来用了*/
tuple的使用方法
make_tuple() //可以用于创建tuple对象
get<0~N>(tuple<>) //0~N表示要访问的下标
存储输入的数据
void Input() //先把数据存起来再说
ios::sync_with_stdio(false);
cin >> N >> M >> K;
schoolN = new int[M];
studentN = new int *[N];
students_sort.resize(N);
AdmissionList = new vector<tuple<int, int, int>>[M];
for (int i = 0; i < M; i++)
int x;
cin >> x;
schoolN[i] = x;
for (int i = 0; i < N; i++)
int n = 2 + K;
int *t = new int[n];
for (int j = 0; j < n; j++)
int x;
cin >> x;
t[j] = x;
studentN[i] = t;
自定义排序模块
对学生通过分数进行排序,决定志愿录取的先后顺序
bool cmp1(tuple<int, int, int> &a, tuple<int, int, int> &b) //如果总成绩不相同,则成绩高的放前面,否则再看初试成绩
return (get<0>(a) > get<0>(b)) || (get<0>(a) == get<0>(b) && get<1>(a) > get<1>(b));
用于对答案编号按照从小到大输出
bool cmp2(tuple<int, int, int> &a, tuple<int, int, int> &b)
return get<2>(a) < get<2>(b);
用于判断两个学生是否完全相同和得到学生编号
inline bool IsEqual(tuple<int, int, int> &a, tuple<int, int, int> &b)
return get<0>(a) == get<0>(b) && get<1>(a) == get<1>(b);
inline int get_val(tuple<int, int, int> &a)
return get<2>(a);
核心模块–答案的更新
void solve()
for (int i = 0; i < N; i++) //先根据成绩把学生排个序(相当于处理录取时候的顺序)
for (int j = 2; j < K + 2; j++)
int sumP = studentN[i][0] + studentN[i][1];
int G = studentN[i][0];
students_sort[i] = make_tuple(sumP, G, i);
sort(students_sort.begin(), students_sort.end(), cmp1); //排好序后,决定了录取的优先顺序
//以下为模拟录取过程
for (int i = 0; i < N; i++)
int node = get<2>(students_sort[i]);
//遍历这个学生的各个志愿
for (int j = 2; j < K + 2; j++)
auto sz = AdmissionList[studentN[node][j]].size();
if (sz < schoolN[studentN[node][j]])
AdmissionList[studentN[node][j]].push_back(students_sort[i]);
break;
else
auto &t = AdmissionList[studentN[node][j]].back();
if (IsEqual(students_sort[i], t)) //如果完全相同则破例录取
AdmissionList[studentN[node][j]].push_back(students_sort[i]);
break;
最后–打印答案
void print()
for (int i = 0; i < M; i++)
auto sz = AdmissionList[i].size();
sort(AdmissionList[i].begin(), AdmissionList[i].end(), cmp2);//打印前先编号从小到大排序
for (int j = 0; j < sz; j++)
if (j != sz - 1)
cout << get_val(AdmissionList[i][j]) << ' ';
else cout << get_val(AdmissionList[i][j]);
if (i != M - 1)
cout << endl;
整合代码提交
效率yyds
#include<bits/stdc++.h>
using namespace std;
int N, M, K;
int *schoolN; //存储每个学校的限额
int **studentN; //存储每个学生的分数和志愿
vector<tuple<int, int, int>> students_sort; //这个只是用来排序的工具
vector<tuple<int, int, int>> *AdmissionList;//存储每个学校的录取名单
//@输入和更新数据
void Input() //先把数据存起来再说
ios::sync_with_stdio(false);
cin >> N >> M >> K;
schoolN = new int[M];
studentN = new int *[N];
students_sort.resize(N);
AdmissionList = new vector<tuple<int, int, int>>[M];
for (int i = 0; i < M; i++)
int x;
cin >> x;
schoolN[i] = x;
for (int i = 0; i < N; i++)
int n = 2 + K;
int *t = new int[n];
for (int j = 0; j < n; j++)
int x;
cin >> x;
t[j] = x;
studentN[i] = t;
//@更新答案
bool cmp1(tuple<int, int, int> &a, tuple<int, int, int> &b)
return (get<0>(a) > get<0>(b)) || (get<0>(a) == get<0>(b) && get<1>(a) > get<1>(b));
inline bool IsEqual(tuple<int, int, int> &a, tuple<int, int, int> &b)
return get<0>(a) == get<0>(b) && get<1>(a) == get<1>(b);
inline int get_val(tuple<int, int, int> &a)
return get<2>(a);
void solve()
for (int i = 0; i < N; i++) //先根据成绩把学生排个序(相当于处理录取时候的顺序)
for (int j = 2; j < K + 2; j++)
int sumP = studentN[i][0] + studentN[i][1];
int G = studentN[i][0];
students_sort[i] = make_tuple(sumP, G, i);
sort(students_sort.begin(), students_sort.end(), cmp1); //排好序后,就根据这个顺序给学生进行录取
//以下为模拟录取过程
for (int i = 0; i < N; i++)
int node = get<2>(students_sort[i]);
for (int j = 2; j < K + 2; j++)
auto sz = AdmissionList[studentN[node][j]].size();
if (sz < schoolN[studentN[node][j]])
AdmissionList[studentN[node][j]].push_back(students_sort[i]);
break;
else
auto &t = AdmissionList[studentN[node][j]].back();
if (IsEqual(students_sort[i], t))
AdmissionList[studentN[node][j]].push_back(students_sort[i]);
break;
//@打印答案
bool cmp2(tuple<int, int, int> &a, tuple<int, int, int> &b)
return get<2>(a) < get<2>(b);
void print()
for (int i = 0; i < M; i++)
auto sz = AdmissionList[i].size();
sort(AdmissionList[i].begin(), AdmissionList[i].end(), cmp2);
for (int j = 0; j < sz; j++)
if (j != sz - 1)
cout << get_val(AdmissionList[i][j]) << ' ';
else cout << get_val(AdmissionList[i][j]);
if (i != M - 1)
cout << endl;
int main()
Input();
solve();
print();
return 0;
题外话
- 讲实话,这个题目感觉就是在写业务代码,实现一个实际功能的。我是比较喜欢这类题型的,感觉这种算法题就比较实用!
pat(advancedlevel)1080.graduateadmission(30)
简单题。#include<cstdio>#include<cstring>#include<cmath>#include<vector>#include<map>#include<stack>#include<queue>#include<string>#include<iostream># 查看详情
pat甲级1043
1043.IsItaBinarySearchTree(25)时间限制400ms内存限制65536kB代码长度限制16000B判题程序Standard作者CHEN,YueABinarySearchTree(BST)isrecursivelydefinedasabinarytreewhichhasthefollowingproperties:Theleftsubtreeofanodecontainso 查看详情
pat甲级1064
1064.CompleteBinarySearchTree(30)时间限制100ms内存限制65536kB代码长度限制16000B判题程序Standard作者CHEN,YueABinarySearchTree(BST)isrecursivelydefinedasabinarytreewhichhasthefollowingproperties:Theleftsubtreeofanodecontai 查看详情
pat甲级1094
1094.TheLargestGeneration(25)时间限制200ms内存限制65536kB代码长度限制16000B判题程序Standard作者CHEN,YueAfamilyhierarchyisusuallypresentedbyapedigreetreewhereallthenodesonthesamelevelbelongtothesamegeneration.Yourtaskisto 查看详情
pat甲级1107
1107.SocialClusters(30)时间限制1000ms内存限制65536kB代码长度限制16000B判题程序Standard作者CHEN,YueWhenregisteronasocialnetwork,youarealwaysaskedtospecifyyourhobbiesinordertofindsomepotentialfriendswiththesamehobbies.A"so 查看详情
pat甲级1044
1044.ShoppinginMars(25)时间限制100ms内存限制65536kB代码长度限制16000B判题程序Standard作者CHEN,YueShoppinginMarsisquiteadifferentexperience.TheMarspeoplepaybychaineddiamonds.Eachdiamondhasavalue(inMarsdollarsM$).Whenmakin 查看详情
pat甲级1076
1076.ForwardsonWeibo(30)时间限制3000ms内存限制65536kB代码长度限制16000B判题程序Standard作者CHEN,YueWeiboisknownastheChineseversionofTwitter.OneuseronWeibomayhavemanyfollowers,andmayfollowmanyotherusersaswell.Henceasocial 查看详情
pat甲级1085
1085.PerfectSequence(25)时间限制300ms内存限制65536kB代码长度限制16000B判题程序Standard作者CAO,PengGivenasequenceofpositiveintegersandanotherpositiveintegerp.Thesequenceissaidtobea"perfectsequence"ifM<=m*pwhereMandmare 查看详情
pat甲级1089
1089.InsertorMerge(25)时间限制200ms内存限制65536kB代码长度限制16000B判题程序Standard作者CHEN,YueAccordingtoWikipedia:Insertionsort iterates,consumingoneinputelementeachrepetition,andgrowingasortedoutputlist.Eachiter 查看详情
pat甲级1003
1003.Emergency(25)时间限制400ms内存限制65536kB代码长度限制16000B判题程序Standard作者CHEN,YueAsanemergencyrescueteamleaderofacity,youaregivenaspecialmapofyourcountry.Themapshowsseveralscatteredcitiesconnectedbysomeroads.A 查看详情
pat甲级1037
1037.MagicCoupon(25)时间限制100ms内存限制65536kB代码长度限制16000B判题程序Standard作者CHEN,YueThemagicshopinMarsisofferingsomemagiccoupons.EachcouponhasanintegerNprintedonit,meaningthatwhenyouusethiscouponwithaproduct,yo 查看详情
pat甲级1013(代码片段)
1013 BattleOverCities(25)(25 分)Itisvitallyimportanttohaveallthecitiesconnectedbyhighwaysinawar.Ifacityisoccupiedbytheenemy,allthehighwaysfrom/towardthatcityareclosed.Wemustknowimmediatelyifw 查看详情
pat甲级1067
1067.SortwithSwap(0,*)(25)时间限制150ms内存限制65536kB代码长度限制16000B判题程序Standard作者CHEN,YueGivenanypermutationofthenumbers0,1,2,...,N-1,itiseasytosorttheminincreasingorder.ButwhatifSwap(0,*)istheONLYoperationtha 查看详情
pat甲级1031
1031.HelloWorldforU(20)时间限制400ms内存限制65536kB代码长度限制16000B判题程序Standard作者CHEN,YueGivenanystringofN(>=5)characters,youareaskedtoformthecharactersintotheshapeofU.Forexample,"helloworld"canbeprintedas:hde 查看详情
pat甲级1057stack
.........)查了一下竟然用到了树状数组,又震惊了一下(PAT甲级有点猛) 先上代码,明天更新作法#include<set> 查看详情
pat甲级考前整理
终于在考前,刷完PAT甲级130道题目,不容易!!!每天沉迷在刷题之中而不能超脱,也是一种境界。PAT甲级题目总的说卡题目的比较多,卡测试点的比较少,有些题目还会有题意混淆,这点就不吐槽了吧。静下心来耍这130道... 查看详情
pat甲级1120
1120.FriendNumbers(20)时间限制400ms内存限制65536kB代码长度限制16000B判题程序Standard作者CHEN,YueTwointegersarecalled"friendnumbers"iftheysharethesamesumoftheirdigits,andthesumistheir"friendID".Forexample,123and51arefrien 查看详情
pat甲级60分啥水平
参考技术A中等水平。截止于2022年9月19日,根据pat甲级的水平定位显示,其答对一道10分的题。答对两道25分的题,这样的水平在pat考试里属于中等。pat指浙江大学计算机程序设计能力考试。浙江大学计算机程序设计能力考试是由... 查看详情