（PTA甲级C语言）1062Talent and Virtue——关于qsort()函数的使用 与 浅拷贝深拷贝问题

1062 Talent and Virtue （25 分）

About 900 years ago, a Chinese philosopher Sima Guang wrote a history book in which he talked about people's talent and

大概在900年前，一个中国的哲学家司马光写了一本历史书，在书里他谈到了关于人们的天赋和

virtue. According to his theory, a man being outstanding in both talent and virtue must be a "sage（圣人）"; being less excellent

美德。根据他的理论，一个在天赋和美德方面都杰出的人一定是个“圣人”（德才兼备）；                   稍次一点（没有那么卓越 ）

but with one's virtue outweighs talent can be called a "nobleman（君子）"; being good in neither is a "fool man（愚人）"; yet a

   但是一个人的美德比天赋nb的可以称为“君子”（德大于才）；两个都不好（德才一般）的就是一个“鱼人”；

fool man is better than a "small man（小人）" who prefers talent than virtue.

然而一个愚人也比那些有才无德的“小人”好（才大于德）。

Now given the grades of talent and virtue of a group of people, you are supposed to rank them according to Sima Guang's theory.

现在，给出一组人的天赋和品德的成绩，你应该根据司马光的理论对他们进行排序。

Input Specification:

Each input file contains one test case. Each case first gives 3 positive integers in a line: N (≤10​^5​​), the total number of people

每一个输入文件至少包括一个测试用例。每个用例首先在一行里给出3个正整数：N（<=10^5）,代表需要被排序的人数；

to be ranked; L (≥60), the lower bound of the qualified grades -- that is, only the ones whose grades of talent and virtue are both

L（>=60）,合格成绩的下界——只有当一个人的成绩德才均

not below this line will be ranked; and H (<100), the higher line of qualification -- that is, those with both grades not below thisL 

不低于这个L线才会被排序；；H（<100）,最高的线的条件——那些两个成绩都不低于这个H线

line are considered as the "sages", and will be ranked in non-increasing order according to their total grades. Those with talent

会被考虑为“圣人”，并且会根据他们的总分来进行非增（递减,a1>=a2）顺序排序。

grades below H but virtue grades not are cosidered as the "noblemen", and are also ranked in non-increasing order according

那些天赋成绩低于H但是美德成绩不低于的（这里是省略句，not are below H）会被认为是“君子”，并且也是根据他们的总分来

to their total grades, but they are listed after the "sages". Those with both grades below H, but with virtue not lower than talent

进行递减排序，但是他们将会在“圣人”后面列出。那些两个成绩都低于H的，但是美德成绩不低于天赋成绩的被认为是

are considered as the "fool men". They are ranked in the same way but after the "noblemen". The rest of people whose grades

“愚人”。他们同样来排序但是在“君子”之后。剩余的人成绩

both pass the L line are ranked after the "fool men".

都过了L线的人会排到“愚人”之后。

Then N lines follow, each gives the information of a person in the format:

然后紧跟着N行，每一行如下格式给出：

ID_Number Virtue_Grade Talent_Grade

where ID_Number is an 8-digit number, and both grades are integers in [0, 100]. All the numbers are separated by a space.

ID_Number 是一个8位的数，并且成绩是[0,100]的整数。所有的数字之间有空格分开。

Output Specification:

The first line of output must give M (≤N), the total number of people that are actually ranked. Then M lines follow, each gives the

第一行必须输出M（<=N）,实际上被排序的人数。之后M的下一行，每一行给出一个人的信息以输入同样的格式，根据排序规

information of a person in the same format as the input, according to the ranking rules. If there is a tie of the total grade, they

则（之后的每一行根据排序规则以输入同样格式输出每个人的信息）。如果总成绩相同（不分胜负，平局），那么他们

must be ranked with respect to their virtue grades in non-increasing order. If there is still a tie, then output in increasing order of

必须根据他们的美德成绩来进行递减排序。如果这也仍然相同（就是说两个人成绩一模一样），那么根据他们的ID递增顺序输出。

their ID's.

Sample Input:

14 60 80
10000001 64 90
10000002 90 60
10000011 85 80
10000003 85 80
10000004 80 85
10000005 82 77
10000006 83 76
10000007 90 78
10000008 75 79
10000009 59 90
10000010 88 45
10000012 80 100
10000013 90 99
10000014 66 60

Sample Output:

12
10000013 90 99
10000012 80 100
10000003 85 80
10000011 85 80
10000004 80 85
10000007 90 78
10000006 83 76
10000005 82 77
10000002 90 60
10000014 66 60
10000008 75 79
10000001 64 90

作者: CHEN, Li

单位: 浙江大学

时间限制: 400 ms

内存限制: 64 MB

代码长度限制: 16 KB

Answer Code：

正确代码：

#include <stdio.h>
#include <stdlib.h>
typedef struct Person
{
    int ID_Number;
    int virtue_Grade,talent_Grade,total_Grade;
    int flag;       //这个，没想到，开始我想的是用四个数组，好麻烦的说
} Person;

int cmp(const void *a,const void *b)
{
    Person *c = (Person*)a;
    Person *d = (Person*)b;
    //这是从小到大。。c<d返回负数，c>d返回正数（可以理解成数轴，返回值为负数的话就是和数轴一样的方向）
    //return (c->flag > d->flag) ? 1 : -1;
    if(c->flag!=d->flag)
        return c->flag - d->flag;
    else if(c->total_Grade!=d->total_Grade)
        return (c->total_Grade > d->total_Grade)? -1 : 1;
    else if(c->virtue_Grade!=d->virtue_Grade)
        return (c->virtue_Grade > d->virtue_Grade) ? -1 : 1;
    else
        return (c->ID_Number>d->ID_Number)? 1 : -1;
}

int main()
{
    int N,L,H;
    int M=0;
    int i=0;
    scanf("%d %d %d",&N,&L,&H);

    Person* p = (Person*)malloc(sizeof(Person)*N);
    //输入，并且分类，1234圣人君子愚人小人
    Person temp;
    for(i=0; i<N; i++)
    {
        scanf("%d %d %d",&(temp.ID_Number),&(temp.virtue_Grade),&(temp.talent_Grade));

        if(temp.talent_Grade>=L && temp.virtue_Grade>=L)
        {
            p[M]=temp;
            p[M].total_Grade = p[M].virtue_Grade+p[M].talent_Grade;
            if(p[M].talent_Grade>=H&&p[M].virtue_Grade>=H)
                p[M].flag = 1;
            else if(p[M].virtue_Grade>=H)
                p[M].flag = 2;
            else if(p[M].virtue_Grade>=p[M].talent_Grade)
                p[M].flag = 3;
            else
                p[M].flag = 4;
            M++;
        }
    }
    //排序，先按类别1--4，
    //然后总分高--低，相等美德高--低，再相等ID小--大
    //要用qsort吗

    //Just try
    //qsort需要编写cmp函数
    qsort(p,M,sizeof(Person),cmp);

    printf("%d\n",M);
    for(i=0; i<M; i++)
    {
        printf("%d %d %d\n",p[i].ID_Number,p[i].virtue_Grade,p[i].talent_Grade);
    }
    return 0;
}

思路：

先将输入的人分为三六九等，结构体里写一个flag，圣人是1，君子是2，愚人是3，小人是4，这样按照flag从小到大进行排序便可实现“圣人，君子，愚人，小人”的四类人的顺序。其次之后再按总成绩，再按品德分，再按ID依次排序。

Summary：

总结：

（不装了我英语不好）哇，真的绝了啊，为什么要有英语。。。翻译题目理解题目就搞了半天TAT

这个题目主要是关于英语。。。=.=算了

这个题目主要是关于qsort()函数的使用，如下：

#include <stdlib.h>

qsort(数组名，数组长度，sizeof(数组元素),比较函数(cmp函数指针));


//其中cmp函数需要自己编写

int cmp(const void * a, const void *b){
    //这里是两个空类型的指针，可以指向任何类型
    ElemType* c = (ElemType*)a;
    ElemType* d = (ElemType*)b;
    if(c!=d){
        //从大到小排序
        return c>d ? -1 : 1;        //这样写比较好记，c>d,返回-1,数轴上-1在1的前面（理解）

        //或者从小到大排序，和上面那个return选其一
        //return c<d ? -1 : 1;        //理解同上，只是把大于小于号换一下
    }    
}

然后举一反三，不只是简单数据类型，结构体也可以排序，如上面这个题的代码。

贴一个大佬博客：https://blog.csdn.net/yisandezhuiqiu/article/details/52101667

同时还可以用判断语句if...else if....else来进行第一关键字排序第二关键字排序。

还有一个地方要强调，就是关于结构体的复制。上面代码中

Person* p = (Person*)malloc(sizeof(Person)*N);
Person temp;    //p[i]和temp都是结构体类型的变量

p[M]=temp;        //直接复制

嗯，这里写了“复制”而不是“赋值”是因为感觉这个词更适合一些。涉及到C语言的浅拷贝和深拷贝。

引用自大佬博客：https://blog.csdn.net/jaihk662/article/details/79757246

浅层复制：

• 实现对象间数据元素的一一对应复制

深层复制：

• 当被复制的对象数据成员是指针类型时，不是复制该指针成员本身，而是将指针所指对象进行复制

 

也就是说，当结构体中含有指针的时候，浅拷贝会使得两个结构体的指针指向同一个地址，从而对第一个结构体的成员进行操作时，指向的这个地址内存就会改变，从而导致第二个结构体里的指针指向的这一个（同一个）地址同时改变，然后第二个结构体的使用就会出错。

如果想要进行深拷贝的话，必须自己写函数，对指针进行特殊处理。

PS：指针的东西都忘得差不多了， 昨天帮人家看程序的时候看了大半天才反应过来。。。指针的声明与赋值问题(Ｔ▽Ｔ)，指针虽好，但一定要搞清再用哦