4 条题解
-
-3
可以在快排那个过程上多加一个变量k,用来表示当前的快排使用的关键字是什么,1表示以总分为关键字,2表示以语文为关键字,3表示以学号为关键字。都是从小到大排序。
在以总分为关键字排完一遍后,找到总分相同的一些连续位置,将这些位置上的数再以语文为关键字再排一遍,然后再找到连续的总分,语文成绩都相同的位置,将这些位置上的数再以学号为关键字从小到大排。
代码呈现
#include<cstdio> #include <stdlib.h> int n,a[20000][4]; void kp(int l,int r,int k){ int i = l,j = r,m = a[(i+j)/2][k]; do { while (a[i][k] < m) i++; while (m < a[j][k]) j--; if (i <= j) { a[0][1] = a[i][1]; a[i][1] = a[j][1]; a[j][1] = a[0][1]; a[0][2] = a[i][2]; a[i][2] = a[j][2]; a[j][2] = a[0][2]; a[0][3] = a[i][3]; a[i][3] = a[j][3]; a[j][3] = a[0][3]; i++;j--; } }while (i <= j); if (l < j) kp(l,j,k); if (i < r) kp(i,r,k); } void input_data(){ scanf("%d",&n); for (int i = 1;i <= n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); a[i][1] = x + y + z; a[i][2] = x; a[i][3] = i; } kp(1,n,1); int i = 1; while (i <= n) { int j = i+1; while (a[i][1] == a[j][1]) j++; kp(i,j-1,2); i = j; } i = 1; while (i <= n) { int j = i+1; while (a[i][1] == a[j][1] && a[i][2] == a[j][2]) j++; kp(i,j-1,3); i = j; } } void output_ans() { for (int i = n;i >= n-4;i--) printf("%d %d\n",a[i][3],a[i][1]); } int main(){ input_data(); output_ans(); return 0; }
信息
- ID
- 446
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 5
- 标签
- 递交数
- 104
- 已通过
- 40
- 上传者