190506 | 成绩排序

短命女 2022-02-04 04:06 234阅读 0赞

想好好准备夏令营机试，以及巩固自己忘得差不多的基础算法，今天起开始每天三道刷题打卡，愿自己能从手生到敲代码飞到溜的转变。

--------------------

**题目描述**

> 查找和排序
> 
> 题目：输入任意（用户，成绩）序列，可以获得成绩从高到低或从低到高的排列,相同成绩 都按先录入排列在前的规则处理。

示例：  
jack 70  
peter 96  
Tom 70  
smith 67

从高到低 成绩  
peter 96  
jack 70  
Tom 70  
smith 67

从低到高

smith 67

jack 70  
Tom 70  
peter 96

--------------------

**思路1：结构体+冒泡排序**

#include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
     
    typedef struct stusco
    {
    	string name;
    	int score;
    }stusco;
     
    void sort(vector<stusco> &s,int n, int method)
    {
    	string tempname;
    	int tempscore;
    	int i=0,j=0;
    	//默认从低排序到高
    	for(i=0;i<n;i++)
    	{
    		for(j=0;j<n-i-1;j++)
    		{
    			if(s[j].score>s[j+1].score)
    			{
    				tempname=s[j].name;
    				tempscore=s[j].score;
    				s[j].name=s[j+1].name;
    				s[j].score=s[j+1].score;
    				s[j+1].name=tempname;
    				s[j+1].score=tempscore;
    			}
    		}
    	}
    	if(method==1)//从低到高
    	{
    		for(i=0;i<n;i++)
    			cout<<s[i].name<<" "<<s[i].score<<endl;
    	}
    	else//从高到低
    	{
    		for(i=n-1;i>=0;i--)
    			cout<<s[i].name<<" "<<s[i].score<<endl;
    	}
     
    }
     
    int main()
    {
    	int n;
    	int method;
    	while(cin>>n>>method){
            vector<stusco> s;
    	stusco student;
    	for(int i=0;i<n;i++)
    	{
    		cin>>student.name>>student.score;
    		s.push_back(student);
    	}
    	sort(s,n,method);
        }
    	
    	return 0;
    }

这位大佬的代码在本地IDE上运行完美，但是在牛客网上只能通过30%的case，我不知道为啥。

**思路2：两个数组+排序**

#include <iostream>
    #include <string>
    using namespace std;
    int main()
    {
        int n;
        while (cin >> n)
            {
        int flag;
        cin >> flag;
        int arr[1000];
        string str[1000];
        for (int i = 0; i < n; i++)
            cin >> str[i] >> arr[i];//利用cin输入特性依次输入姓名与成绩
        int j;
     
        for (int i = 0; i < n; i++)
        {
            int max = arr[0], min = arr[0];
            int x = 0;
            for (j = 0; j < n; j++)
            {
                if (flag == 0)
                {
                    if (max<arr[j])//找到最大的成绩，并取出下标
                    {
                        max = arr[j];
                        x = j;
                    }
                }
                else if (flag == 1)
                {
                    if (min>arr[j])
                    {
                        min = arr[j];
                        x = j;
                    }
                }
            }
            cout << str[x] << " " << arr[x] << endl;
            if (flag == 0)
                arr[x] = -1;
            else if (flag == 1)
                arr[x] = 10000;
        }
        }
        return 0;
    }

另一位大佬的解法，更简单粗暴，通过oj。

**思路3**

//感觉很多人都用排序的方法，这样时间复杂度最少O(nlogn)
    //其实可以直接弄一个列为101的二维vector<vector<string>>，因为这里分数是整数
    //且分布在0-100之间，把所有名字分别放入对应列的行里，
    //再顺序输出就行了，时间复杂度为O(n)
        #include<iostream>
        #include<vector>
    	#include<string>
        using namespace std;
     
        int main() {
        int n;
        int method;
        vector<vector<string>> stu(101);
        while (cin >> n >> method) {
            string name = "";
            int score;
            for (int i = 0; i < n; i++) {
                cin >> name >> score;
                stu[score].push_back(name);//将对应分数的名字放入对应列的容器里
            }
           if (method) {//method为1就升序输出
               for (int i = 0; i <= 100; i++) {
                   if (stu[i].size()) {
                       for (int j = 0; j < stu[i].size(); j++) {
                           cout << stu[i][j] << " " << i << endl;
                       }
                   }
               }
           }
           else {//为0就降序输出
               for (int i = 100; i >= 0; i--) {
                   if (stu[i].size()) {
                       for (int j = stu[i].size() - 1; j >= 0; j--) {
                           cout << stu[i][j] << " " << i << endl;
                       }
                   }
               }
           }
        }
        return 0;
     
        }

这位大佬的思路特别棒，但是也是本地IDE完美通过 但是牛客网上oj无法通过。

--------------------

知识点：  
1 struct 结构体

*  C中：

typedef struct Student
    　　　　{ 
    　　　　int a;
    　　　　}Stu;//结构体类型
    　int main(){ 
    		　Stu s;
    		　s.a=1;
    　}

*  c++中：

struct   Student  
    　　　　{  
    　　　　int   a;  
    　　　　}stu1;//stu1是一个变量  　
    	int main()
    		{
    		  stu1.a=1;
    		}

2 vector数组与二维数组

*  需要包含头文件： `#include<vector>`
 *  一般习惯无参构造：`vector<int> a;`
 *  常用属性与函数：[https://blog.csdn.net/sevenjoin/article/details/81901259][https_blog.csdn.net_sevenjoin_article_details_81901259]
 *  二维数组构造：`vector<vector<int> > array(m); //这个m一定不能少，int也可以变换为其他类型`

`在这里插入代码片`注意点：  
本地IDE可以直接编译通过 但是牛客网在线系统需要循环输入。

--------------------

Reference：  
\[1\] C++ vector的用法总结（整理）  
[https://blog.csdn.net/sevenjoin/article/details/81901259][https_blog.csdn.net_sevenjoin_article_details_81901259]  
\[2\] 关于vector定义二维数组的问题  
[https://blog.csdn.net/oNever\_say\_love/article/details/50763238][https_blog.csdn.net_oNever_say_love_article_details_50763238]  
\[3\] struct和typedef struct彻底明白了  
[https://www.cnblogs.com/qyaizs/articles/2039101.html][https_www.cnblogs.com_qyaizs_articles_2039101.html]

[https_blog.csdn.net_sevenjoin_article_details_81901259]: https://blog.csdn.net/sevenjoin/article/details/81901259
[https_blog.csdn.net_oNever_say_love_article_details_50763238]: https://blog.csdn.net/oNever_say_love/article/details/50763238
[https_www.cnblogs.com_qyaizs_articles_2039101.html]: https://www.cnblogs.com/qyaizs/articles/2039101.html