【PAT B1015】德才论（C语言）

#include <stdio.h>

//第１位表示四类考生，接下来３位表示总分，再接着３位表示德分，后８位表示准考证号
#define x 100000000000000
#define y 100000000000
#define z 100000000

int getStandard(long long array[], int i, int j) {
    // 基准数据
    long long key = array[i];
    while (i < j) {
        // 因为默认基准是从左边开始，所以从右边开始比较
        // 当队尾的元素大于等于基准数据 时,就一直向前挪动 j 指针
        while (i < j && array[j] <= key) {
            j--;
        }
        // 当找到比 array[i] 小的时，就把后面的值 array[j] 赋给它
        if (i < j) {
            array[i] = array[j];
        }
        // 当队首元素小于等于基准数据 时,就一直向后挪动 i 指针
        while (i < j && array[i] >= key) {
            i++;
        }
        // 当找到比 array[j] 大的时，就把前面的值 array[i] 赋给它
        if (i < j) {
            array[j] = array[i];
        }
    }
    // 跳出循环时 i 和 j 相等,此时的 i 或 j 就是 key 的正确索引位置
    // 把基准数据赋给正确位置
    array[i] = key;
    return i;
}

void QuickSort(long long array[], int low, int high) {
    // 开始默认基准为 low
    if (low < high) {
        // 分段位置下标
        int standard = getStandard(array, low, high);
        // 递归调用排序
        // 左边排序
        QuickSort(array, low, standard - 1);
        // 右边排序
        QuickSort(array, standard + 1, high);
    }
}

int main() {

    int N, L, H;
    scanf("%d %d %d", &N, &L, &H);
    long long id, d, c ,sum;//定义考号，德分，才分，才德总分
    int count = 0;//count为上线学生人数，
    long long stu[100001], temp,lev;//lev为学生类别

    for (int i = 0; i < N; i++) {
        scanf("%lld %lld %lld", &id, &d, &c);
        if (d >= L && c >= L) {
            sum = d + c;
            if (d >= H && c >= H) {
                lev = 4;//归为第一类考生
            }
            else if (d >= H) {
                lev = 3;//归为第二类考生
            }
            else if (d >= c) {
                lev = 2;//归为第三类考生
            }
            else {
                lev = 1;//归为其他类考生
            }
            stu[count] = lev * x + sum * y + d * z + z - id;//考生类别优先，其次总分，再次德分，最次考号升序
            count++;
        }
    }

    QuickSort(stu, 0, count - 1);//快速排序

    printf("%d\n", count);
    for (int i = 0; i < count; i++) {
        sum = stu[i] % x / y;
        id = z - stu[i] % z;
        d = stu[i] % y / z;
        c = sum - d;
        printf("%lld %lld %lld\n", id, d, c);

    }
    return 0;
}