难题来了-世界500强通信公司的笔试题-学校师资调整问题

bikkuri

大家好！
我有一个问题向大家请教。
是一个世界500强通信公司的笔试题。大牛们请出手！
期待jason680大神的彩色代码！

有6所学校A-F，每个学校有6位老师，每位老师允许教3门科目（科目种类不定）。
例如：
学校A：
第一位老师A1，教的是：中文、英文和政治。
第二位老师A2，教的是：物理、化学和生物。
。。。
第六位老师A6，教的是：地理、历史和几何。

学校B：
第一位老师B1，教的是：数学、生物和物理。
第二位老师B2，教的是：政治、历史和中文。
。。。
第六位老师B6，教的是：计算机、会计和贸易

学校C、D、E、F依此类推。

36位老师的教学能力情况如下表所示（教学科目以两位字母科目代码表示）：

1. A1: BJ FF PG
   
2. A2: FG BJ RX
   
3. A3: JG FG SM
   
4. A4: PF JG SM
   
5. A5: PF MZ BS
   
6. A6: SB MZ JF
   
7. B1: JG PF PG
   
8. B2: PF RX SB
   
9. B3: BJ BS PG
   
10. B4: PJ BS BJ
    
11. B5: PG SM FF
    
12. B6: JG SM PG
    
13. C1: JG FG GD
    
14. C2: BJ JG SB
    
15. C3: PG BS FG
    
16. C4: JG SB PF
    
17. C5: BS FF BJ
    
18. C6: FG SM PJ
    
19. D1: PG FG GD
    
20. D2: RX PG JG
    
21. D3: FG JG BS
    
22. D4: SB BS FG
    
23. D5: BJ BS SB
    
24. D6: BJ PF FF
    
25. E1: PG PF PJ
    
26. E2: SB PF GD
    
27. E3: JF GD JG
    
28. E4: BJ FF PF
    
29. E5: MZ SB PF
    
30. E6: SB FF GD
    
31. F1: BJ SM PF
    
32. F2: SB PJ RX
    
33. F3: BS FG PJ
    
34. F4: MZ FG RX
    
35. F5: FG BJ BS
    
36. F6: RX SM FG

复制代码

现在教育部出台了新的政策，希望对这些师资力量进行调整，将这些老师按照以下规则进行重新组合。
1、每个学校中必须有6位老师，并且含有从1到6六个数字，比如学校A可以有：C1、F2、B3、D4、C5、A6这六名老师组成；
2、一个学校中教某一门科目的老师越多，则这门科目的师资力量越强。
如果一个学校里有3位老师教中文，则该校为中文三星学校，教育部给予4万块钱奖金；
如果一个学校里有4位老师教数学，则该校为数学四星学校，教育部给予6万块钱奖金；
如果一个学校里有5位老师教物理，则该校为物理五星学校，教育部给予8万块钱奖金；
如果一个学校里有6位老师教英文，则该校为英文六星学校，教育部给予10万块钱奖金；
奖金可以叠加，如果一个学校同时为中文三星学校和数学四星学校，则教育部给予4+6=10万块钱奖金；
3、6个学校按照A-F的按顺序由六位校长依次进行老师的选择。

第一位进行选择的校长A，可以从36位老师中选择6位老师，为了使学校A可以从教育部得到的奖金最多，他会怎么选择呢？
第二位进行选择的校长B，可以从剩下的30位老师中选择6位老师，为了使学校B可以从教育部得到最多的奖金，他会怎么选择呢？
。。。
请打印出重新组合后的六个学校的老师组合情况以及各个学校分别能获得多少奖金。

Herowinter

回复 1# bikkuri


弱弱地问下, 中文 数学 物理 英文 科目的两位字母缩写分别是什么?

reyleon

回复 2# Herowinter


    目测什么中文 英文 物理只是一个类比啦

zsszss0000

1.    A1A2A3A4A5A6B1B2B3B4B5B6C1C2C3C4C5C6D1D2D3D4D5D6E1E2E3E4E5E6F1F2F3F4F5F6 total
   
2. RX:0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1  6
   
3. JF:0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0  2
   
4. JG:0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0  10
   
5. SM:0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1  7
   
6. SB:0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 0 0  10
   
7. BS:0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0  10
   
8. PF:0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 1 1 0 1 0 0 0 0 0  11
   
9. PG:1 0 0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0  9
   
10. GD:0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0  5
    
11. FF:1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0  6
    
12. BJ:1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0  11
    
13. PJ:0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0  5
    
14. MZ:0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0  4
    
15. FG:0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1  12

复制代码

这个是整理出来的每一门课都有哪些老师教授的表格，大家看看接下来应该怎么做？

reyleon

这尼玛不会做, 艹

ly5066113

回复 5# reyleon


算法问题，笨办法循环枚举肯定能做出来。

bikkuri

搬个小板凳，坐等各位大神教我~

回复 6# ly5066113


   

Windows19

        

zsszss0000

1. #include <iostream>
   
2. using namespace std;
   
3. #define NUM_SCHOOL 6
   
4. #define NUM_TEACHER 6
   
5. #define NUM_COURSE  14
   
6. #define NUM_COURSE_EACH 3
   
7. 
   
8. #define        RX 0
   
9. #define        JF 1
   
10. #define        JG 2
    
11. #define        SM 3
    
12. #define        SB 4
    
13. #define        BS 5
    
14. #define        PF 6
    
15. #define        PG 7
    
16. #define        GD 8
    
17. #define        FF 9
    
18. #define        BJ 10
    
19. #define        PJ 11
    
20. #define        MZ 12
    
21. #define        FG 13
    
22. 
    
23. /*
    
24.         A1: BJ FF PG
    
25.         A2: FG BJ RX
    
26.         A3: JG FG SM
    
27.         A4: PF JG SM
    
28.         A5: PF MZ BS
    
29.         A6: SB MZ JF
    
30.         B1: JG PF PG
    
31.         B2: PF RX SB
    
32.         B3: BJ BS PG
    
33.         B4: PJ BS BJ
    
34.         B5: PG SM FF
    
35.         B6: JG SM PG
    
36.         C1: JG FG GD
    
37.         C2: BJ JG SB
    
38.         C3: PG BS FG
    
39.         C4: JG SB PF
    
40.         C5: BS FF BJ
    
41.         C6: FG SM PJ
    
42.         D1: PG FG GD
    
43.         D2: RX PG JG
    
44.         D3: FG JG BS
    
45.         D4: SB BS FG
    
46.         D5: BJ BS SB
    
47.         D6: BJ PF FF
    
48.         E1: PG PF PJ
    
49.         E2: SB PF GD
    
50.         E3: JF GD JG
    
51.         E4: BJ FF PF
    
52.         E5: MZ SB PF
    
53.         E6: SB FF GD
    
54.         F1: BJ SM PF
    
55.         F2: SB PJ RX
    
56.         F3: BS FG PJ
    
57.         F4: MZ FG RX
    
58.         F5: FG BJ BS
    
59.         F6: RX SM FG
    
60. */
    
61. 
    
62. 
    
63. const int aaa[NUM_SCHOOL][NUM_TEACHER][NUM_COURSE_EACH]=
    
64. {
    
65. 
    
66.         {
    
67.                 { BJ,FF,PG },
    
68.                 { FG,BJ,RX },
    
69.                 { JG,FG,SM },
    
70.                 { PF,JG,SM },
    
71.                 { PF,MZ,BS },
    
72.                 { SB,MZ,JF },
    
73.         },
    
74.         {
    
75.                 { JG,PF,PG },
    
76.                 { PF,RX,SB },
    
77.                 { BJ,BS,PG },
    
78.                 { PJ,BS,BJ },
    
79.                 { PG,SM,FF },
    
80.                 { JG,SM,PG },
    
81.         },
    
82.         {
    
83.                 { JG,FG,GD },
    
84.                 { BJ,JG,SB },
    
85.                 { PG,BS,FG },
    
86.                 { JG,SB,PF },
    
87.                 { BS,FF,BJ },
    
88.                 { FG,SM,PJ },
    
89.         },
    
90. 
    
91.         {
    
92.                 { PG,FG,GD },
    
93.                 { RX,PG,JG },
    
94.                 { FG,JG,BS },
    
95.                 { SB,BS,FG },
    
96.                 { BJ,BS,SB },
    
97.                 { BJ,PF,FF },
    
98.         },
    
99. 
    
100.         {
     
101.                 { PG,PF,PJ },
     
102.                 { SB,PF,GD },
     
103.                 { JF,GD,JG },
     
104.                 { BJ,FF,PF },
     
105.                 { MZ,SB,PF },
     
106.                 { SB,FF,GD },
     
107.         },
     
108. 
     
109.         {
     
110.                 { BJ,SM,PF },
     
111.                 { SB,PJ,RX },
     
112.                 { BS,FG,PJ },
     
113.                 { MZ,FG,RX },
     
114.                 { FG,BJ,BS },
     
115.                 { RX,SM,FG },
     
116.        
     
117.         },
     
118. };
     
119. 
     
120. int aval_teacher_table[NUM_SCHOOL][NUM_TEACHER];
     
121. int cord_course[NUM_COURSE][NUM_SCHOOL*NUM_TEACHER];
     
122. 
     
123. int init_aval_teacher_table(int aval_teacher_table[][NUM_TEACHER])
     
124. {
     
125.         int i=0;
     
126.         int j=0;
     
127. 
     
128.         for(i=0;i<NUM_SCHOOL;i++)
     
129.         {
     
130.                 for(j=0;j<NUM_TEACHER;j++)
     
131.                 {
     
132.                         aval_teacher_table[i][j]=1;
     
133.                 }
     
134.         }
     
135. 
     
136.         return 1;
     
137. }
     
138. int init_course_table(int cord_course[][NUM_SCHOOL*NUM_TEACHER])
     
139. {
     
140.         int i=0;
     
141.         int j=0;
     
142. 
     
143.         for(i=0;i<NUM_COURSE;i++)
     
144.         {
     
145.                 for(j=0;j<NUM_SCHOOL*NUM_TEACHER;j++)
     
146.                 {
     
147.                         cord_course[i][j]=0;
     
148.                 }
     
149.         }
     
150. 
     
151.         return 1;
     
152. }
     
153. int chosed_teacher[6];
     
154. int best_chosed_teacher[6];
     
155. int best_price;
     
156. 
     
157. int check_chose_teacher(int teacher[])
     
158. {
     
159.         int ret = 0;///<默认失败
     
160.         int tmp[6]={0,0,0,0,0,0};
     
161. 
     
162.         int i=0;
     
163.         for(i=0;i<6;i++)
     
164.         {
     
165.                 tmp[teacher[i]%6]=1;       
     
166.         }
     
167. 
     
168.         for(i=0;i<6;i++)
     
169.         {
     
170.                 if(tmp[i]==0)
     
171.                         break;
     
172.         }
     
173.         if(i==6)
     
174.         {
     
175. //                cout<<"teacher arrangement is valid!"<<endl;
     
176.                 /* 说明6个序号都存在，此时还要添加 */
     
177.                 return 1;
     
178.         }
     
179.         else
     
180.         {
     
181. //                cout<<"teacher arrangement is not  valid!"<<endl;
     
182.                 return 0;       
     
183.         }
     
184. }
     
185. 
     
186. int update_best_teacher(int teacher[])
     
187. {
     
188.         int i;
     
189.         int j;
     
190.         int num;
     
191.         int tmp_price=0;
     
192.         int tmp_index;
     
193. //        for(i=0;i<6;i++)
     
194. //        {
     
195. //                cout<<"teacher is "<<teacher[i]<<"\t";
     
196. //        }
     
197. //        cout<<endl;
     
198.         /* 此处需要用到course_teacher表格 */
     
199. 
     
200.         for(i=0;i<NUM_COURSE;i++)
     
201.         {
     
202.                 num=0;
     
203.                 for(j=0;j<6;j++)
     
204.                 {
     
205.                         tmp_index=teacher[j];
     
206.                         if(cord_course[i][tmp_index])
     
207.                         {
     
208.                                 num++;
     
209.                         }
     
210.                 }
     
211. 
     
212.                 if(num==3)
     
213.                 {
     
214.                         tmp_price+=4;
     
215.                 }
     
216.                 else if(num==4)
     
217.                 {
     
218.                         tmp_price+=6;
     
219.                 }
     
220.                 else if(num==5)
     
221.                 {
     
222.                         tmp_price+=8;
     
223.                 }
     
224.                 else if(num==6)
     
225.                 {
     
226.                         tmp_price+=10;
     
227.                 }
     
228.                 else
     
229.                 {
     
230.                         ///<do nothing
     
231.                 }
     
232.         }
     
233. 
     
234.         if(tmp_price>=best_price)
     
235.         {
     
236.                 for(i=0;i<6;i++)
     
237.                 {
     
238.                         cout<<"teacher is "<<teacher[i]<<"\t";
     
239.                 }
     
240.                 cout<<"total price is "<<tmp_price;
     
241.                 cout<<endl;
     
242.                 for(i=0;i<6;i++)
     
243.                 {
     
244.                         best_chosed_teacher[i]=teacher[i];
     
245.                 }
     
246.                 best_price=tmp_price;
     
247.         }
     
248. }
     
249. 
     
250. int zuhe(int k,int n)
     
251. {
     
252.         int x1;
     
253.         int x2;
     
254.         int x3;
     
255.         int x4;
     
256.         int x5;
     
257.         int x6;
     
258. 
     
259.         for (int x1 = 0; x1 <= n-k; x1++)
     
260.                 for (int x2 = x1+1; x2 <= n-k+1; x2++)
     
261.                         for (int x3 = x2+1; x3 <= n-k+2; x3++)
     
262.                                 for (int x4 = x3+1; x4 <= n-k+3; x4++)
     
263.                                         for (int x5 = x4+1; x5 <= n-k+4; x5++)
     
264.                                                 for (int x6 = x5+1; x6 <= n-k+5; x6++)
     
265.                                                 {
     
266.                                                         chosed_teacher[0]=x1;
     
267.                                                         chosed_teacher[1]=x2;
     
268.                                                         chosed_teacher[2]=x3;
     
269.                                                         chosed_teacher[3]=x4;
     
270.                                                         chosed_teacher[4]=x5;
     
271.                                                         chosed_teacher[5]=x6;
     
272. //                                                        cout<<x1<<" "<<x2<<" "<<x3<<" "<<x4<<" "<<x5<<" "<<x6<<endl;
     
273.                                                         if(check_chose_teacher(chosed_teacher))
     
274.                                                         {
     
275.                                                                 update_best_teacher(chosed_teacher);
     
276.                                                         }
     
277.                                                         else
     
278.                                                         {
     
279.                                                                 break;       
     
280.                                                         }
     
281.                                                 }
     
282. }
     
283. 
     
284. 
     
285. int main ( int argc, char *argv[] )
     
286. {
     
287.         best_price=0;
     
288.         init_aval_teacher_table(aval_teacher_table);
     
289.         init_course_table(cord_course);
     
290. 
     
291.         int i=0;
     
292.         int j=0;
     
293.         int k=0;
     
294.         int tmp=0;
     
295. 
     
296.         for(i=0;i<NUM_SCHOOL;i++)
     
297.         {
     
298.                 for(j=0;j<NUM_TEACHER;j++)
     
299.                 {
     
300.                         for(k=0;k<NUM_COURSE_EACH;k++)
     
301.                         {
     
302.                                 cord_course[aaa[i][j][k]][6*i+j]=1;       
     
303.                        
     
304.                         }
     
305.                 }
     
306.         }
     
307.         cout<<"   "<<"A1A2A3A4A5A6B1B2B3B4B5B6C1C2C3C4C5C6D1D2D3D4D5D6E1E2E3E4E5E6F1F2F3F4F5F6 total"<<endl;
     
308.         for(i=0;i<NUM_COURSE;i++)
     
309.         {
     
310.                 switch(i)
     
311.                 {
     
312.                         case 0:
     
313.                                 cout<<"RX:";
     
314.                                 break;
     
315.                         case 1:
     
316.                                 cout<<"JF:";
     
317.                                 break;
     
318.                         case 2:
     
319.                                 cout<<"JG:";
     
320.                                 break;
     
321.                         case 3:
     
322.                                 cout<<"SM:";
     
323.                                 break;
     
324.                         case 4:
     
325.                                 cout<<"SB:";
     
326.                                 break;
     
327.                         case 5:
     
328.                                 cout<<"BS:";
     
329.                                 break;
     
330.                         case 6:
     
331.                                 cout<<"PF:";
     
332.                                 break;
     
333.                         case 7:
     
334.                                 cout<<"PG:";
     
335.                                 break;
     
336.                         case 8:
     
337.                                 cout<<"GD:";
     
338.                                 break;
     
339.                         case 9:
     
340.                                 cout<<"FF:";
     
341.                                 break;
     
342.                         case 10:
     
343.                                 cout<<"BJ:";
     
344.                                 break;
     
345.                         case 11:
     
346.                                 cout<<"PJ:";
     
347.                                 break;
     
348.                         case 12:
     
349.                                 cout<<"MZ:";
     
350.                                 break;
     
351.                         case 13:
     
352.                                 cout<<"FG:";
     
353.                                 break;
     
354.                         default:
     
355. 
     
356.                                 break;
     
357.                 }
     
358.                 tmp=0;
     
359. 
     
360.                 for(j=0;j<NUM_SCHOOL*NUM_TEACHER;j++)
     
361.                 {
     
362.                         if(cord_course[i][j])
     
363.                         {
     
364.                                 tmp++;
     
365.                         }
     
366.                        
     
367.                         cout<<cord_course[i][j]<<" ";
     
368.                 }
     
369.                 cout<<" "<<tmp<<endl;
     
370.         }
     
371. 
     
372.         zuhe(6,36);
     
373. 
     
374.         cout<<"the best teacher arrangement is "<<endl;
     
375.         for(i=0;i<6;i++)
     
376.         {
     
377.                 cout<<best_chosed_teacher[i]<<"\t";
     
378.         }
     
379.         cout<<endl;
     
380.         cout<<"the price is "<<endl;
     
381.         cout<<best_price<<endl;
     
382. 
     
383. 
     
384.         return 1;
     
385. }/* end of function main  */
     

复制代码

1. 
   
2.    A1A2A3A4A5A6B1B2B3B4B5B6C1C2C3C4C5C6D1D2D3D4D5D6E1E2E3E4E5E6F1F2F3F4F5F6 total
   
3. RX:0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1  6
   
4. JF:0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0  2
   
5. JG:0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0  10
   
6. SM:0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1  7
   
7. SB:0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 0 0  10
   
8. BS:0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0  10
   
9. PF:0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 1 1 0 1 0 0 0 0 0  11
   
10. PG:1 0 0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0  9
    
11. GD:0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0  5
    
12. FF:1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0  6
    
13. BJ:1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0  11
    
14. PJ:0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0  5
    
15. MZ:0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0  4
    
16. FG:0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1  12
    
17. teacher is 0    teacher is 1    teacher is 2    teacher is 3    teacher is 4    teacher is 5    total price is 0
    
18. teacher is 0    teacher is 1    teacher is 2    teacher is 3    teacher is 10   teacher is 11   total price is 14
    
19. teacher is 0    teacher is 1    teacher is 2    teacher is 3    teacher is 34   teacher is 35   total price is 14
    
20. teacher is 0    teacher is 1    teacher is 2    teacher is 23   teacher is 27   teacher is 28   total price is 14
    
21. teacher is 0    teacher is 1    teacher is 2    teacher is 33   teacher is 34   teacher is 35   total price is 16
    
22. teacher is 0    teacher is 1    teacher is 5    teacher is 14   teacher is 21   teacher is 22   total price is 16
    
23. teacher is 0    teacher is 1    teacher is 5    teacher is 20   teacher is 21   teacher is 22   total price is 16
    
24. teacher is 0    teacher is 1    teacher is 8    teacher is 9    teacher is 34   teacher is 35   total price is 16
    
25. teacher is 0    teacher is 1    teacher is 8    teacher is 21   teacher is 34   teacher is 35   total price is 16
    
26. teacher is 0    teacher is 1    teacher is 8    teacher is 23   teacher is 27   teacher is 28   total price is 16
    
27. teacher is 0    teacher is 1    teacher is 8    teacher is 33   teacher is 34   teacher is 35   total price is 16
    
28. teacher is 0    teacher is 1    teacher is 9    teacher is 14   teacher is 34   teacher is 35   total price is 16
    
29. teacher is 0    teacher is 1    teacher is 9    teacher is 20   teacher is 34   teacher is 35   total price is 16
    
30. teacher is 0    teacher is 1    teacher is 9    teacher is 32   teacher is 34   teacher is 35   total price is 16
    
31. teacher is 0    teacher is 1    teacher is 11   teacher is 14   teacher is 21   teacher is 22   total price is 16
    
32. teacher is 0    teacher is 1    teacher is 14   teacher is 21   teacher is 34   teacher is 35   total price is 16
    
33. teacher is 0    teacher is 1    teacher is 14   teacher is 33   teacher is 34   teacher is 35   total price is 16
    
34. teacher is 0    teacher is 1    teacher is 20   teacher is 21   teacher is 34   teacher is 35   total price is 16
    
35. teacher is 0    teacher is 1    teacher is 20   teacher is 33   teacher is 34   teacher is 35   total price is 16
    
36. teacher is 0    teacher is 1    teacher is 21   teacher is 32   teacher is 34   teacher is 35   total price is 16
    
37. teacher is 0    teacher is 1    teacher is 32   teacher is 33   teacher is 34   teacher is 35   total price is 16
    
38. teacher is 0    teacher is 2    teacher is 3    teacher is 13   teacher is 34   teacher is 35   total price is 16
    
39. teacher is 0    teacher is 3    teacher is 10   teacher is 11   teacher is 19   teacher is 20   total price is 16
    
40. teacher is 0    teacher is 5    teacher is 8    teacher is 13   teacher is 21   teacher is 22   total price is 16
    
41. teacher is 0    teacher is 5    teacher is 8    teacher is 19   teacher is 21   teacher is 22   total price is 16
    
42. teacher is 0    teacher is 5    teacher is 9    teacher is 22   teacher is 31   teacher is 32   total price is 16
    
43. teacher is 0    teacher is 7    teacher is 8    teacher is 11   teacher is 21   teacher is 22   total price is 16
    
44. teacher is 0    teacher is 7    teacher is 8    teacher is 23   teacher is 27   teacher is 28   total price is 16
    
45. teacher is 0    teacher is 7    teacher is 8    teacher is 27   teacher is 28   teacher is 29   total price is 16
    
46. teacher is 0    teacher is 7    teacher is 16   teacher is 23   teacher is 26   teacher is 27   total price is 16
    
47. teacher is 0    teacher is 8    teacher is 9    teacher is 19   teacher is 22   teacher is 23   total price is 16
    
48. teacher is 0    teacher is 8    teacher is 11   teacher is 13   teacher is 21   teacher is 22   total price is 18
    
49. teacher is 0    teacher is 8    teacher is 19   teacher is 23   teacher is 27   teacher is 28   total price is 18
    
50. teacher is 0    teacher is 9    teacher is 16   teacher is 23   teacher is 31   teacher is 32   total price is 18
    
51. teacher is 1    teacher is 2    teacher is 30   teacher is 33   teacher is 34   teacher is 35   total price is 20
    
52. teacher is 2    teacher is 3    teacher is 6    teacher is 7    teacher is 10   teacher is 11   total price is 20
    
53. teacher is 6    teacher is 8    teacher is 11   teacher is 13   teacher is 21   teacher is 22   total price is 20
    
54. teacher is 6    teacher is 15   teacher is 25   teacher is 26   teacher is 28   teacher is 29   total price is 20
    
55. teacher is 12   teacher is 13   teacher is 20   teacher is 21   teacher is 22   teacher is 23   total price is 20
    
56. teacher is 12   teacher is 15   teacher is 25   teacher is 26   teacher is 28   teacher is 29   total price is 20
    
57. the best teacher arrangement is
    
58. 12      15      25      26      28      29
    
59. the price is
    
60. 20

复制代码

teacher is 1    teacher is 2    teacher is 30   teacher is 33   teacher is 34   teacher is 35   total price is 20
teacher is 2    teacher is 3    teacher is 6    teacher is 7    teacher is 10   teacher is 11   total price is 20
teacher is 6    teacher is 8    teacher is 11   teacher is 13   teacher is 21   teacher is 22   total price is 20
teacher is 6    teacher is 15   teacher is 25   teacher is 26   teacher is 28   teacher is 29   total price is 20
teacher is 12   teacher is 13   teacher is 20   teacher is 21   teacher is 22   teacher is 23   total price is 20
teacher is 12   teacher is 15   teacher is 25   teacher is 26   teacher is 28   teacher is 29   total price is 20
teacher is 1    teacher is 2    teacher is 30   teacher is 33   teacher is 34   teacher is 35   total price is 20
这个组合表示
A2 A3 F1 F4 F5 F6

上面这些组合的和为20,如果A学校的校长，任选其中一种选择的话，那么B校长要在此基础之上，进行一个选择。

我觉得这道题目，还可以有下面几种变形：
1、保持原来要求不变，但是要求总体得到的奖励最大（即六所学校得到的奖励之和最大）
2、保持原来要求不变，但是要求总体得到的奖励最小（即A要选择一个其他5家得到的和最小，B要在此基础之上选择一个使得其他四家得到的最小，以此类推）

jason680

1. $ awk -F'[ :]+' '{N=substr($1,2);for(n=2;n<=NF;n++){if(!a[$n,"max"]++)t[++c]=$n;a[$n,$1]=1;if(!a[$n,N]++)a[$n,"all"]++}}END{for(n=1;n<=c;n++){s=t[n];print s,a[s,"max"],a[s,"all"];for(m=65;m<65+6;m++){E=sprintf("%c",m);printf E" ";for(k=1;k<=6;k++)printf("%d",a[s,E k]);print""}print""}}' FILE | awk -vg=5 'BEGIN{RS="";FS="\n"}{for(n=1;n<=NF;n++)a[n]=sprintf("%s %-10s  ",a[n],$n)}NR%g==0{for(n=1;n<=NF;n++){print a[n];a[n]=""}print""}END{for(n=1;n<=NF;n++)print a[n]}'
   
2. BJ 11 6      FF 6 4       PG 9 5       FG 12 6      RX 6 3      
   
3. A 110000     A 100000     A 100000     A 011000     A 010000   
   
4. B 001100     B 000010     B 101011     B 000000     B 010000   
   
5. C 010010     C 000010     C 001000     C 101001     C 000000   
   
6. D 000011     D 000001     D 110000     D 101100     D 010000   
   
7. E 000100     E 000101     E 100000     E 000000     E 000000   
   
8. F 100010     F 000000     F 000000     F 001111     F 010101   
   
9. 
   
10. JG 10 5      SM 7 5       PF 11 5      MZ 4 3       BS 10 3     
    
11. A 001100     A 001100     A 000110     A 000011     A 000010   
    
12. B 100001     B 000011     B 110000     B 000000     B 001100   
    
13. C 110100     C 000001     C 000100     C 000000     C 001010   
    
14. D 011000     D 000000     D 000001     D 000000     D 001110   
    
15. E 001000     E 000000     E 110110     E 000010     E 000000   
    
16. F 000000     F 100001     F 100000     F 000100     F 001010   
    
17. 
    
18. SB 10 4      JF 2 2       PJ 5 5       GD 5 4      
    
19. A 000001     A 000001     A 000000     A 000000   
    
20. B 010000     B 000000     B 000100     B 000000   
    
21. C 010100     C 000000     C 000001     C 100000   
    
22. D 000110     D 000000     D 000000     D 100000   
    
23. E 010011     E 001000     E 100000     E 011001   
    
24. F 010000     F 000000     F 011000     F 000000

复制代码

subject total best_solution
BJ 11 6
A 110000
B 001100
C 010010
D 000011
E 000100

GD 5 4      
A 000000   
B 000000   
C 100000   
D 100000   
E 011001   
F 000000
ex: best_solution
best_solution (4) = C1,E2,E3,x4,x5,E6
best_solution (4) = D1,E2,E3,x4,x5,E6

由 total与best_solution最多(FG,BJ,PF,....)先选...
best_solution少于3个(JF)不用管

先这样......