一道題目，原題完整敘述如下：
Description
A competition was just over. It had 3 problems and n players. Eachplayer had an ID number from 1 to n. The ?nal rank wasdecided by the total score of the 3 problems. The higher the total score was,the higher a player ranked (the smaller the rank number). If two players gotthe same total score, the one with the smaller ID number got a higher rank.We've known for each problem, how much score each player might get if he didn'tsolve totally wrong (if solved totally wrong, the player got zero in theproblem). However, we don’t know whether a player did get score in a problem.For a predicted ?nal rank, you need to judge if the rank is possible.
Input
Input contains several cases. For each case, the ?rst line is an integer n, (n <= 16384) to indicate the number ofplayers, followed by n lines, the ith of which contains three real numbers a,b, c (0<=a, b, c < 1000. a, b and c have 2 decimal places at most.) torespectively indicate the score of each problem Player i might get if he didn’tsolve totally wrong. Another line containing n integers follows to indicate theplayer ID number in the order from rank 1st to rank nth .
The last caseis followed by a line containing only a zero.
Output
No solution" (quotes for clarity).
Sample Input
3
100 200 300
100 200 300
100 200 300
1 2 3
3
100 200 300
100 200 300
100 200 300
3 2 1
0
Sample Output
Case 1: 600.00
Case 2: 400.00
這道題的來源是：ACM Beijing 2006-E
自己寫了代碼，提交以後AC了，代碼如下：
1. #include <stdio.h> 2. #include <stdlib.h> 3. 4. #define PROBLEM_NUM 3 5. 6. int main () 7. { 8. int n = 0; // number of players 9. float** grades = NULL; // possible grades if not totally wrong 10. float results[1000]; 11. int* rank = NULL; // predicted rankings 12. float grade = 0, temp = 0, temp1 = 0; 13. int m = 0; // case counter: case m 14. int i = 0, j = 0, k = 0; // loop counter 15. 16. scanf("%d", &n); 17. while (n) { 18. rank = (int*)malloc(sizeof(int) * n); 19. grades = (float**)malloc(sizeof(float*) * n); 20. for (i = 0; i < n; i++) 21. grades[i] = (float*)malloc(sizeof(float) * PROBLEM_NUM); 22. 23. // get input 24. for (i = 0; i < n; i++) 25. for (j = 0; j < PROBLEM_NUM; j++) { 26. scanf("%f", &temp); 27. getchar(); // get rid of white spaces 28. /* Insertion Sort */ 29. for (k = j; k > 0 && temp < grades[i][k]; k--) 30. grades[i][k] = grades[i][k-1]; 31. grades[i][k] = temp; 32. } 33. 34. for (i = 0; i < n; getchar(), i++) 35. scanf("%d", &rank[i]); 36. 37. // judge the rank and find the score 38. grade = grades[rank[0]-1][0] + grades[rank[0]-1][1] + grades[rank[0]-1][2]; 39. temp = 0; 40. for (i = 1; i < n; i++) { 41. if (rank[i] > rank[i-1]) { 42. for (j = 0; j < 8 && temp <= grade; j++) { 43. switch (j) { // value of "temp" increases with "j" 44. case 0: temp = 0; break; 45. case 1: temp = grades[i][0]; break; 46. case 2: temp = grades[i][1]; break; 47. case 3: 48. temp = grades[i][0] + grades[i][1] >= grades[i][2] ? grades[i][2] : grades[i][0] + grades[i][1]; 49. break; 50. case 4: 51. temp = grades[i][0] + grades[i][1] <= grades[i][2] ? grades[i][2] : grades[i][0] + grades[i][1]; 52. break; 53. case 5: temp = grades[i][0] + grades[i][2]; break; 54. case 6: temp = grades[i][1] + grades[i][2]; break; 55. case 7: temp = grades[i][0] + grades[i][1] + grades[i][2]; break; 56. default: break; 57. } 58. temp1 = temp <= grade ? temp : temp1; 59. } 60. } 61. else { 62. for (j = 0; j < 8 && temp < grade; j++) { 63. switch (j) { // value of "temp" increases with "j" 64. case 0: temp = 0; break; 65. case 1: temp = grades[i][0]; break; 66. case 2: temp = grades[i][1]; break; 67. case 3: 68. temp = grades[i][0] + grades[i][1] >= grades[i][2] ? grades[i][2] : grades[i][0] + grades[i][1]; 69. break; 70. case 4: 71. temp = grades[i][0] + grades[i][1] <= grades[i][2] ? grades[i][2] : grades[i][0] + grades[i][1]; 72. break; 73. case 5: temp = grades[i][0] + grades[i][2]; break; 74. case 6: temp = grades[i][1] + grades[i][2]; break; 75. case 7: temp = grades[i][0] + grades[i][1] + grades[i][2]; break; 76. default: break; 77. } 78. temp1 = temp < grade ? temp : temp1; 79. } 80. } 81. 82. if (j == 1) break; 83. 84. grade = temp1; 85. temp = temp1 = 0; 86. } 87. if (i==n && j!= 1) 88. results[m] = grade; 89. else 90. results[m] = -1; 91. m ++; 92. 93. // release storage 94. for (i = 0; i < n; i++) 95. free(grades[i]); 96. free(grades); 97. free(rank); 98. 99. scanf("%d", &n); // player number of next case 100. } 101. 102. for (i = 0; i < m; i++) { 103. if (results[i] != -1) 104. printf("Case %d: %.2f\n", i, results[i]); 105. else 106. printf("Case %d: No solution\n"); 107. } 108. //free(results); 109. 110. return 0; 111. }
我的想法是在讀取數據的時候進行插入排序，然後判斷時利用switch...case...語句從最小值開始嘗試所有可能情況。
這個代碼有很多地方處理得不太好。
1. 使用了一個定長數組（足夠大）results[1000]，這個是用來存放結果的。
2. 不能很方便的變化問題個數，當PROBLEM_NUM不為3時，不能直接使用這個代碼了；這個主要是受限制於判斷部分的switch...case...語句。我采用的處理方法是從最小的可能得分開始嘗試，直到最大的可能，有點窮舉的味道，我想肯定會有更好的算法。
3. 幾乎同樣的代碼重復出現，就是那兩個switch...case...語句那裡。
歡迎大家提出想法和意見，讓我來學習~
本文出自 “WhatWhyHow” 博客
