菠萝的成绩单--多元素快排

快排不仅利用一种元素进行排序，例如int大小排序，char字典序排序，同时可以进行多元素排序，例如按照质量升序排序，质量相同时按照价格降序排序，此时也可以利用快排进行排序，例如3下面这道题目：

菠萝的成绩单

Problem Description

考完试以后，菠萝获得了一个含有 n 个成绩的成绩单，他要把成绩按照从高到低排序，如果成绩相同则按照学生编号从小到大排序。 老师为了检验菠萝是否把成绩排序对了，会询问前 m 高的成绩及该学生的编号，你能帮菠萝回答老师的询问吗？

Input

输入数据有多组（数据组数不超过 10），到 EOF 结束。 对于每组数据： •第一行输入成绩的个数 n 以及 m (1 <= n <= 100000, 1 <= m <= n) •接下来的 n 行，每行输入 2 个正整数，分别为学生编号 id (1 <= id <= n)，成绩 ai (1 <= ai <= 10000) 当 n 和 m 同时为 0 时结束程序。

Output

对于每组数据： •第一行输出 “Case #x:” (输出不包括引号，且冒号后无空格)，x 表示当前为第几组数据 •之后输出 m 行。每行格式按照 “编号 成绩” 的格式输出

Example Input

3 1 1 1 2 2 3 3 5 3 4 2 2 2 1 1 3 3 5 2 0 0

Example Output

Case #1: 3 3 Case #2: 3 3 2 2 4 2

经过分析，题目意思很清楚，按照成绩降序排序，成绩相同时按照学生编号升序排序。所以此题为多元素的快排。 完整代码如下：

#include <stdio.h> #include <stdlib.h> struct node { int score; int id; }k[100050]; void pai(struct node a[], int y, int z) { int key1 = a[y].score, key2 = a[y].id, i = y, j = z; if(i > j) return; while(i < j) { while(i < j && (a[j].score < key1 || (a[j].score == key1 && a[j].id > key2))) { j--; } a[i] = a[j]; while(i < j && (a[i].score > key1 || (a[i].score == key1 && a[i].id < key2))) { i++; } a[j] = a[i]; } a[i].score = key1; a[i].id = key2; pai(a, i + 1, z); pai(a, y, i - 1); } int main() { int n, m, i, x = 1; while(~scanf("%d %d", &n, &m)) { if(n == 0 && m == 0) break; printf("Case #%d:\n", x++); for(i = 0; i <= n - 1; i++) { scanf("%d %d", &k[i].id, &k[i].score); } pai(k, 0, n - 1); for(i = 0; i <= m - 1; i++) { printf("%d %d\n", k[i].id, k[i].score); } } return 0; }