20200613-04 PAT 甲级试题 03 List Grades-蒲公英云

20200613-04 PAT 甲级试题 03 List Grades

思路讲解

本题的核心在于排序(降序)
所以可以选用比较常见的几种排序算法，如冒泡，快排，插入，选择等等
快速排序详解
冒泡法详解
插入排序法

这里选用递归类型的快速排序法，具体详细看代码

源码

#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <tuple>
#include <iostream>
using namespace std;
void sort_quick_r(vector<tuple<string, string, int>> & array, int left, int right)
{ 
    int tmp = get<2>(array[left]);
    auto v = array[left];
    int p = left;
    int i = left, j = right;
    while (i <= j) { 
        while (get<2>(array[j]) <= tmp && j >= p)
            j--;
        if (j >= p) { 
            array[p] = array[j];
            p = j;
        }
        while (get<2>(array[i]) >= tmp && i <= p)
            i++;
        if (i <= p) { 
            array[p] = array[i];
            p = i;
        }
    }
    array[p] = v;
    if (p - left > 1)
        sort_quick_r(array, left, p-1);
    if (right - p > 1)
        sort_quick_r(array, p+1, right);
}
int main() { 
    int n_counts { 0};
    int max_grade { 0}, min_grade { 0};
    //这个是 C++ 的一个类型 tuple 一个结构体，具体可以查找官方文档
    vector<tuple<string, string, int>> student_records;
    //读取输入值
    scanf("%d", &n_counts);
    char temp_name[10];
    char temp_id[10];
    int temp_grade { 0};
    while (n_counts--) { 
        scanf("%s %s %d", temp_name, temp_id, &temp_grade);
        student_records.push_back(make_tuple(temp_name, temp_id, temp_grade));
        //对于两个数组进行初始化
        memset(temp_id, 0, sizeof (temp_id));
        memset(temp_name, 0, sizeof (temp_name));
    }
    scanf("%d %d", &min_grade, &max_grade);
    //排序 降序
    sort_quick_r(student_records, 0, student_records.size() - 1);
    //去除数据范围之外的数据
    //记录打印数量
    auto printf_count { 0};
    for (const auto & temp : student_records) { 
        auto _grade = get<2>(temp);
        //打印满足要求的值
        if (_grade <= max_grade && _grade >= min_grade) { 
            cout << get<0>(temp) << " " << get<1>(temp) << endl;
            printf_count++;
        }
    }
    //没有任何符合要求的项，输出 NONE
    if (0 == printf_count) { 
        cout << "NONE" <<endl;
    }
    return 0;
}