20200613-04 PAT 甲级试题 03 List Grades

ゝ一纸荒年。 2023-02-17 11:18 20阅读 0赞

#### 思路讲解 ####

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

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

#### 源码 ####

#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;
    }

## 推荐课程 ##

尹成老师带你学算法

数据结构核心原理与算法应用

[Link 1]: https://blog.csdn.net/qq_24890953/article/details/106731835
[Link 2]: https://blog.csdn.net/qq_24890953/article/details/106729676
[Link 3]: https://blog.csdn.net/qq_24890953/article/details/106757848