9.2 德才论

本文主要是介绍9.2 德才论，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

宋代史学家司马光在《资治通鉴》中有一段著名的“德才论”：“是故才德全尽谓之圣人，才德兼亡谓之愚人，德胜才谓之君子，才胜德谓之小人。凡取人之术，苟不得圣人，君子而与之，与其得小人，不若得愚人。”

现给出一批考生的德才分数，请根据司马光的理论给出录取排名。

输入格式：

输入第一行给出 3 个正整数，分别为：N（≤105），即考生总数；L（≥60），为录取最低分数线，即德分和才分均不低于 L 的考生才有资格被考虑录取；H（<100），为优先录取线——德分和才分均不低于此线的被定义为“才德全尽”，此类考生按德才总分从高到低排序；才分不到但德分到优先录取线的一类考生属于“德胜才”，也按总分排序，但排在第一类考生之后；德才分均低于 H，但是德分不低于才分的考生属于“才德兼亡”但尚有“德胜才”者，按总分排序，但排在第二类考生之后；其他达到最低线 L 的考生也按总分排序，但排在第三类考生之后。

随后 N 行，每行给出一位考生的信息，包括：准考证号、德分、才分，其中准考证号为 8 位整数，德才分为区间 [0, 100] 内的整数。数字间以空格分隔。

输出格式：

输出第一行首先给出达到最低分数线的考生人数 M，随后 M 行，每行按照输入格式输出一位考生的信息，考生按输入中说明的规则从高到低排序。当某类考生中有多人总分相同时，按其德分降序排列；若德分也并列，则按准考证号的升序输出。

经过：

今天数据结构实验课的题目，乍一看感觉挺简单，思路就是先对所有合格考生的总分从小到大排序，这个过程可以使用快速排序实现；再根据四个分数标准把排好序的数据分成四类，遇到同类且总分相同的则比较德育分，德育分相同再按准考证号升序，这个过程可以采用链表，在链表插入过程中再对同总分的数据进一步排序，可采用插入排序实现，因为此时数据基本有序，插入排序在这种情况下时间复杂度较小，比较适合。

很快啊，代码就扣出来了，最近考试周要来了，事挺多，所以实验课要速战速决！必须立刻拿下！提交！

哎咋回事啊？（经过漫长的debug）哦双向链表忘了改后继结点的前驱指针了

改好，提交！

哎咋又超时了？（经过漫长的debug）哦遍历时把前导和后随指针的起始点都设在链表的尾节点上了，结果尾插的时候插成闭环了😰。

改好，提交！

赢了！然而一抬头天都黑完了😓，明天大物小测还没复习，感觉要寄😓。

太晚了，先开睡，明天的明天再说！💤

参考代码：

#include<stdlib.h>
#include<stdio.h>
#include<string.h>//定义存储考生考号和分数的结构体
typedef struct SCORE{char num[9];int d, c;
}INFO;//定义链表
typedef struct CHAINLISTNODE{struct SCORE item;struct CHAINLISTNODE *next;struct CHAINLISTNODE *before;
} CLN,*CLNptr;
typedef struct CHAINLIST{CLNptr head;CLNptr rear;
} CL;
void push(CL *cl,INFO ins){//链表插入操作，插入时对总分相同的依次按德育分降序和学号升序进行排序CLNptr p = (CLNptr)malloc(sizeof(CLN));CLNptr tra = cl->rear,ptra=NULL;while(tra->before&&tra->item.c+tra->item.d==ins.c+ins.d&&tra->item.d<ins.d){ptra = tra;tra = tra->before;}while(tra->before&&tra->item.c+tra->item.d==ins.c+ins.d&&tra->item.d==ins.d&&strcmp(tra->item.num,ins.num)>0){ptra = tra;tra = tra->before;}p->before = tra;p->next = tra->next;p->item = ins;tra->next = p;if(ptra)ptra->before = p;if(tra==cl->rear)cl->rear = p;
}
CL init(){//链表初始化操作CLNptr p = (CLNptr)malloc(sizeof(CLN));p->next = NULL;p->before = NULL;CL cl;cl.head = p;cl.rear = p;return cl;
}
void traverse(CL cl){//链表遍历输出CLNptr p = cl.head->next;while(p!=NULL){printf("%s %d %d\n", p->item.num, p->item.d, p->item.c);p = p->next;}
}//快速排序
void T(INFO *x,INFO *y){INFO tmp;tmp = *x;*x = *y;*y = tmp;
}
int partition(INFO *list,int left,int right){INFO key = list[left];while (left<right){while (left<right&&list[right].c+list[right].d<=key.c+key.d)--right;T(list + left, list + right);while (left<right&&list[left].c + list[left].d>=key.c+key.d)++left;T(list + left, list + right);}T(list + left, &key);return left;
}
void quicksort(INFO *list,int left,int right){if(left<right){int mid = partition(list, left, right);if(left<mid-1)quicksort(list, left, mid - 1);if(right>mid+1)quicksort(list, mid + 1, right);}
}int main(){int n, L, H;scanf("%d%d%d", &n, &L, &H);INFO *list = (INFO *)malloc(sizeof(INFO) * n);int len = 0;for (int i = 0; i < n;++i){int d, c;char num[9];scanf("%s%d%d", num, &d, &c);if(d>=L&&c>=L){strcpy(list[len].num, num);list[len].c = c;list[len].d = d;++len;}}quicksort(list, 0, len - 1);CL level[4];//对四个类别建桶for (int i = 0; i < 4;++i){level[i] = init();}for (int i = 0; i < len;++i){if(list[i].d>=H){if(list[i].c>=H){//德才兼备入桶0push(level + 0, list[i]);}else{//德胜才入桶1push(level + 1, list[i]);}}else{if(list[i].c<H&&list[i].d>=list[i].c){//才德兼亡但尚有德胜才入桶2push(level + 2, list[i]);}else{//其余入桶3push(level + 3, list[i]);}}}printf("%d\n", len);for (int i = 0; i < 4;++i){traverse(level[i]);}return 0;
}

又

c语言标准库好像有自带快速排序，刚刚才知道🐊🐊

用qsort重写一遍：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct SCORE{char num[9];int d, c, sum, level;
}*ptr;
int compare(const void *X,const void *Y){ptr x = (ptr)X, y = (ptr)Y;if(x->level<y->level){return -1;}else if(x->level==y->level){if(x->sum>y->sum){return -1;}else if(x->sum==y->sum){if(x->d>y->d){return -1;}else if(x->d==y->d){if(strcmp(x->num,y->num)<0){return -1;}}}}return 1;
}
int main(){int n, L, H;scanf("%d%d%d", &n, &L, &H);ptr list = (ptr)malloc(sizeof(struct SCORE) * n);int len = 0;for (int i = 0; i < n;++i){int d, c;char num[9];scanf("%s%d%d", num, &d, &c);if(d>=L&&c>=L){strcpy(list[len].num, num);list[len].c = c;list[len].d = d;list[len].sum = c + d;if(c>=H&&d>=H){list[len].level = 0;}else if(d>=H){list[len].level = 1;}else if(d>=c){list[len].level = 2;}else{list[len].level = 3;}++len;}}qsort(list, len, sizeof(struct SCORE), compare);printf("%d\n",len);for (int i = 0; i < len;++i){printf("%s %d %d\n", list[i].num, list[i].d, list[i].c);}return 0;
}

这篇关于9.2 德才论的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！