成绩排序发表时间：2022-10-27 20:16 成绩排序 问题描述 有 n 名学生，它们的学号分别是 1,2,…,n。这些学生都选修了邓老师的算法训练营、数据结构训练营这两门课程。 学期结束了，所有学生的课程总评都已公布，所有总评分数都是 [0,100] 之间的整数。巧合的是，不存在两位同学，他们这两门课的成绩都完全相同。 邓老师希望将这些所有的学生按这两门课程的总分进行降序排序，特别地，如果两位同学的总分相同，那邓老师希望把算法训练营得分更高的同学排在前面。由于上面提到的巧 合，所以，这样排名就可以保证没有并列的同学了。 邓老师将这个排序任务交给了他的助教。可是粗心的助教没有理解邓老师的要求，将所有学生按学号进行了排序。 邓老师希望知道，助教的排序结果中，存在多少逆序对。 如果对于两个学生 (i,j) 而言，i 被排在了 j 前面，并且i 本应被排在 j 的后面，我们就称 (i,j) 是一个逆序对。 请你先帮邓老师把所有学生按正确的顺序进行排名，再告诉他助教的错误排名中逆序对的数目。 输入格式 第一行一个整数 n，表示学生的个数。 第 2 行到第 n+1 行，每行 2 个用空格隔开的非负整数，第 i+1 行的两个数依次表示学号为 i 的同学的算法训练营、数据结构训练营的总评成绩。 输格式 输出包含 n+1 行。 前 n 行表示正确的排序结果，每行 4 个用空格隔开的整数，第 i 行的数依次表示排名为 i 的同学的学号、总分、算法训练营成绩、数据结构训练营成绩。第 n+1 行一个整数，表示助教的错误排名中逆序对的数目。 样例输入 样例输 3199100 99 118095 85 218090 90 2 样例解释 学号为 3 的同学总分为 199，是最高的，所以他应该排第一名。 学号为 1 的同学虽然总分与学号为 2 的同学一致，但是他的算法训练营成绩更高，所以在排名规则下更胜一筹。 原错误排名中的逆序对数目为 2 ，这些逆序对分别为 (1,3) 和 (2,3)。 数据范围 对于 25% 的数据，保证 n=3。对于 50% 的数据，保证 n≤10。 对于另外 25% 的数据，保证所有同学的总分两两不同。 对于 100% 的数据，保证 n≤5,000 ，且保证不存在成绩完全相同的学生。时间限制：10 sec 空间限制：256 MB 提示 [可以使用起泡排序将所有学生进行排名。] [善良的助教提醒你，在起泡排序的过程中，每次交换都会使逆序对数目减少 1 哦！想一想，为什么？] [聪明的助教还告诉你，这道题可以设计出时间复杂度为 O(nlogn) 的算法。这会在今后的课程中涉及到。] 代码 #include<iostream> #include<queue>
using namespace std;
int ni = 0;//逆序对
class Student//定义学生类,存储学生的学号\总成绩\算法训练营成绩\数据结构成绩 { public: int stNum, totalSocre, firSocre, secSocre; Student(int num, int socre1, int socre2)//构造函数 { stNum = num; totalSocre = socre1 + socre2; firSocre = socre1; secSocre = socre2; } };
bool operator<(Student a, Student b)//自定义priority_queue的比较 { //通过依次比较totalSocre, firSocre, secSocre来获取a与b比较的结果 //不可通过a与b的比较来获取逆序对，因为priority_queue是类二叉堆，无法一一进行比较， 故所获得的逆序对有无 if (b.totalSocre > a.totalSocre) { return true; } else if (b.totalSocre == a.totalSocre) { if (b.firSocre > a.firSocre) { return true; } else if (b.firSocre == a.firSocre) { if (b.secSocre > a.secSocre) { return true; } else return false; } else return false; } else return false; }
//通过对学号进行冒泡排序来获取逆序对(获取逆序对不可通过快速排序，例如{3,2,5,1}通过快速排序获得的是错误的逆序对) //其中sourceArr是通过priority_queue传出的学号数组，即通过学号的逆序对来获得总的逆序对 //冒泡排序总的时间复杂度为O(n^2) void BubbleSort(int num[],int n) { for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (num[i] > num[j]) ni++; } } }
int main() { priority_queue<Student> pq; int n; cin >> n; int tempFir, tempSec; for (int i = 0; i < n; i++) { cin >> tempFir >> tempSec; Student st(i,tempFir,tempSec); pq.emplace(st);//通过比较，将st按由大到小的方式压入priority_queue中(总的时间复杂度为O(nlogn)) } int* disoredrNum=new int[n];//通过priority_queue排序后所输出的st.stNum int* tempNum = new int[n];//归并排序的辅助数组 int i = 0; while (!pq.empty()) { Student st = pq.top(); cout << st.stNum+1 << ' ' << st.totalSocre << ' ' << st.firSocre << ' ' << st.secSocre << endl; disoredrNum[i] = st.stNum + 1; i++; pq.pop(); } BubbleSort(disoredrNum,n); cout << ni << endl; return 0; }
|