PTA1015 純C語言解法

這裡直接上答案，後面給出部分解析。

#include "stdio.h"
#include "stdlib.h"
#define MAX_ARR 100000

typedef struct Node{
	int no; // including of 8 numbers
	int a; // moral score
	int b; // talent score
	int sum; // total score
	int level; // from 1 to 5
}ListNode, *PNode;
int cmp(const void *a,const void *b){
	PNode n1, n2;
	n1 = (PNode)a;
	n2 = (PNode)b;
	if(n1->level!= n2->level) return n1->level-n2->level  ;
	else if(n1->sum != n2->sum) return n2->sum - n1->sum;
	else if(n1->a != n2->a) return n2->a - n1->a;
	else return n1->no - n2->no;
}
void my_print(ListNode s[], int j)
{
	int i;
	for(i=0; i<j; i++)
		printf("%d %d %d\n", s[i].no, s[i].a, s[i].b);
}
int main(){
	int N,L,H,size=0,tmp_no,tmp_a,tmp_b;
	ListNode List[MAX_ARR],new_node;
	scanf("%d %d %d",&N,&L,&H);
	while(N-->0){
		scanf("%d %d %d",&tmp_no,&tmp_a,&tmp_b);
		if(tmp_a<L||tmp_b<L){
			continue;
		} else {
			new_node.no = tmp_no;
			new_node.a = tmp_a;
			new_node.b = tmp_b;
			new_node.sum = tmp_a+tmp_b;
		}
		if(tmp_a>=H && tmp_b>=H){
			new_node.level = 1;
		}else if(tmp_a >= H){
			new_node.level = 2;
		}else if(tmp_a >= tmp_b){
			new_node.level = 3;
		}else
			new_node.level = 4;
		List[size++] = new_node;
	}
	qsort(List,size,sizeof(ListNode),cmp);
	printf("%d\n",size);
	my_print(List,size);
	return 0;
}
           

1、為什麼使用結構體

不用多說，在面向過程的C語言中，結構體是為數不多的可以用來存儲多種元素的容器，根據這個題目的要求，不可避免的要是用結構體。

2、為什麼使用結構體數組而不是連結清單

這個後面會給出解答，筆者嘗試使用單向連結清單完成該題目，但是對于連結清單和指針不熟悉的朋友來說，使用單向連結清單會帶來極大的難度，在調試上浪費很多時間。推薦使用數組，可以直覺的進行調試，另一方面，C語言标準庫裡給出了優秀的排序算法，減少造輪子。連結清單的排序算法難度不低，如果想使用連結清單，請回顧下連結清單排序。另外，該題測試用例規模較大，沒有一個足夠強度的排序算法，将會很容易産生逾時，甚至錯誤。

3、qsort 函數的使用

這個請自行搜尋，難度不大，很容易了解，但是像了解排序原理的朋友可以嘗試去看下源碼。

4、cmp 函數的編寫

注意cmp函數将會影響排序算法的執行時間，一個好而高效的cmp将會極大節約算法運作時間。

總結以下需要注意的點：

1. 答題過程中盡量不要造輪子，一是容易出錯，二是效率可能會低。
2. 多掌握一些C庫函數的用法，在考試或者比賽過程中能夠節約時間，為解決核心問題提供備援。