題目分析：
本題的演算法并不復雜，主要是要搞清楚資料的存盤方式（選擇一種合適的方式存盤每個學生的四個成績很重要）這里由于N的范圍為10^6，故選擇結構體來存放對應下標為學生的id（N只有2000的范圍，所以結構體開10^6其實有點浪費空間），再者對于每個學生的每種成績的排名我們通過下面的這種方式可以巧妙得到（而且單科成績是會出現重復的，即并列的情況）：
獲取排名的方法：其實很簡單，由于會出現并列單科成績的方式，且單個學生的成績是存盤在結構體里的，通過多次排序的方式去解決這道題目是不太合適的，這里用四個陣列a[]，c[]，m[]，e[]存放每種成績的出現的次數（因為成績只有0~100的可能）,而我們想要知道單科的成績的排名就只需要對比該分數高的分數共有多少個+1就是該id的同學的該單科的成績排名（這里已經回避了考慮并列的情況，十分方便！），至此我們就用num_a，num_c，num_m，num_e四個數存放了每次查詢的id的四科成績的排名，最后只要選擇一個最小的，有同樣最小時選擇權重最高的（a > c > m > e），代碼中展示了一種巧妙的判斷方法，讀者在下面閱讀時請稍加思考
1 #include<iostream> 2 #include<string.h> 3 using namespace std; 4 5 int a[105]; 6 int c[105]; 7 int m[105]; 8 int e[105]; 9 int vis[1000000]; 10 struct Node{ 11 int A, C, M, E; 12 }k[1000000]; 13 14 int main(){ 15 int N, M; 16 while(scanf("%d%d", &N, &M) != EOF){ 17 memset(vis, 0, sizeof(vis)); 18 memset(a, 0, sizeof(a)); 19 memset(c, 0, sizeof(c)); 20 memset(m, 0, sizeof(m)); 21 memset(e, 0, sizeof(e)); 22 for(int i = 1; i <= N; i++){ 23 int id; 24 scanf("%d", &id); 25 scanf("%d%d%d", &k[id].C, &k[id].M, &k[id].E); 26 k[id].A = (k[id].C + k[id].M + k[id].E) / 3; 27 vis[id] = 1; 28 a[k[id].A]++; 29 c[k[id].C]++; 30 m[k[id].M]++; 31 e[k[id].E]++; 32 } 33 for(int i = 1; i <= M; i++){ 34 int id; 35 scanf("%d", &id); 36 if(vis[id] == 0) printf("N/A\n"); 37 else{ 38 //查詢該id的四個成績的排名 39 int num_a = 0; 40 int num_c = 0; 41 int num_m = 0; 42 int num_e = 0; 43 for(int j = 100; j > k[id].A; j--) num_a += a[j]; 44 for(int j = 100; j > k[id].C; j--) num_c += c[j]; 45 for(int j = 100; j > k[id].M; j--) num_m += m[j]; 46 for(int j = 100; j > k[id].E; j--) num_e += e[j]; 47 //此時得到的num是比該查詢id的單一每種成績高的個數 id的每種成績的排名要再+1（這樣的方式默認為存在并列情況） 48 //接下來要選擇四個排名中最小的 如果有同樣小的則按照權重a > c > m > e 49 if(num_a <= num_c && num_a <= num_m && num_a <= num_e){ 50 printf("%d A\n", num_a + 1); 51 }else if(num_c <= num_m && num_c <= num_e){ 52 printf("%d C\n", num_c + 1); 53 }else if(num_m <= num_e){ 54 printf("%d M\n", num_m + 1); 55 }else{ 56 printf("%d E\n", num_e + 1); 57 } 58 } 59 } 60 } 61 return 0; 62 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/139972.html
標籤：其他
上一篇：牛客練習賽53 A-E