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

bikkuri

非常感谢您的回复。
您的程序非常精彩。
能不能在输出结果中加上获奖的科目类别呢？
比如：
F1: BJ SM PF A2: FG BJ RX F3: BS FG PJ B4: PJ BS BJ F5: FG BJ BS C6: FG SM PJ 20=(4BJ+4BJ+3BS+3FG)
谢谢！

回复 11# ly5066113


   

bikkuri

谢谢您写的这么长的应该是perl程序？
不过我执行好像出错了？

1. [root@gin:~]# perl test.pl
   
2. Quantifier follows nothing in regex; marked by <-- HERE in m/* <-- HERE
   
3.         A1: BJ FF PG
   
4.         A2: FG BJ RX
   
5.         A3: JG FG SM
   
6.         A4: PF JG SM
   
7.         A5: PF MZ BS
   
8.         A6: SB MZ JF
   
9.         B1: JG PF PG
   
10.         B2: PF RX SB
    
11.         B3: BJ BS PG
    
12.         B4: PJ BS BJ
    
13.         B5: PG SM FF
    
14.         B6: JG SM PG
    
15.         C1: JG FG GD
    
16.         C2: BJ JG SB
    
17.         C3: PG BS FG
    
18.         C4: JG SB PF
    
19.         C5: BS FF BJ
    
20.         C6: FG SM PJ
    
21.         D1: PG FG GD
    
22.         D2: RX PG JG
    
23.         D3: FG JG BS
    
24.         D4: SB BS FG
    
25.         D5: BJ BS SB
    
26.         D6: BJ PF FF
    
27.         E1: PG PF PJ
    
28.         E2: SB PF GD
    
29.         E3: JF GD JG
    
30.         E4: BJ FF PF
    
31.         E5: MZ SB PF
    
32.         E6: SB FF GD
    
33.         F1: BJ SM PF
    
34.         F2: SB PJ RX
    
35.         F3: BS FG PJ
    
36.         F4: MZ FG RX
    
37.         F5: FG BJ BS
    
38.         F6: RX SM FG
    
39. */ at test.pl line 60.
    
40. [root@gin:~]#

复制代码

请恕我眼拙，难道是c语言还是python？不会是lua吧？
另外我想问一下就是穷举的话应该不止您列出来的那40种组合吧？

如果校长A有多种选择可以得到一样的最大奖金的话，应该选择使总体得到奖励最大，也就是总体师资力量最强的组合，这也是教育部出台新政策的初衷。



回复 9# zsszss0000


   

bikkuri

谢谢jason680大神的回复和您的彩色代码。
不过您的程序计算的是每一门学科的组合吧？
能不能得到每个学校的老师的组合呢？
谢谢。

回复 10# jason680


   

zsszss0000

C++代码，用g++编译运行，我这个仅仅考虑了A校长，收益最大的情况。
如果没有校长都选择对自己最有利的情况，在此基础之上再选择对其他校长最有利的情况，我觉得会有一些复杂


回复 22# bikkuri


   

ly5066113

回复 21# bikkuri

1. #! /bin/awk -f
   
2. 
   
3. BEGIN{
   
4.         z[6] = 10
   
5.         z[5] = 8
   
6.         z[4] = 6
   
7.         z[3] = 4
   
8. }
   
9. {
   
10.         if(NR%6==1) a[$0] ++
    
11.         else if(NR%6==2) b[$0] ++
    
12.         else if(NR%6==3) c[$0] ++
    
13.         else if(NR%6==4) d[$0] ++
    
14.         else if(NR%6==5) e[$0] ++
    
15.         else f[$0] ++
    
16. }
    
17. END{
    
18.         for(u=6;u>0;u--)
    
19.         {
    
20.                 v = 0
    
21.                 w = ""
    
22.                 g = ""
    
23.                 for(i in a)
    
24.                         for(j in b)
    
25.                                 for(k in c)
    
26.                                         for(l in d)
    
27.                                                 for(m in e)
    
28.                                                         for(n in f)
    
29.                                                         {
    
30.                                                                 r = i" "j" "k" "l" "m" "n
    
31.                                                                 s = 0
    
32.                                                                 h = ""
    
33.                                                                 for(t=1;t<=split(r,x);t++)
    
34.                                                                         if(x[t]!~/:/)
    
35.                                                                                 y[x[t]] ++
    
36.                                                                 for(t in y)
    
37.                                                                         if(y[t] in z)
    
38.                                                                         {
    
39.                                                                                 s += z[y[t]]
    
40.                                                                                 h = h ? h "+" y[t] t : y[t] t
    
41.                                                                         }
    
42.                                                                 delete y
    
43.                                                                 if( s > v )
    
44.                                                                 {
    
45.                                                                         v = s
    
46.                                                                         w = r
    
47.                                                                         g = h
    
48.                                                                 }
    
49.                                                         }
    
50.                 print w, v "=(" g ")"
    
51.                 for(i in a) if(index(w, i)) delete a[i]
    
52.                 for(i in b) if(index(w, i)) delete b[i]
    
53.                 for(i in c) if(index(w, i)) delete c[i]
    
54.                 for(i in d) if(index(w, i)) delete d[i]
    
55.                 for(i in e) if(index(w, i)) delete e[i]
    
56.                 for(i in f) if(index(w, i)) delete f[i]
    
57.         }
    
58. }
    

复制代码

Windows19

弱弱的路过，弱弱的问下，是不是换了工作了

reyleon

回复 9# zsszss0000

是啊, 要把所有可能的奖金方案全部打印出来啊.

reyleon

笨的不能再笨的方法了, 打印所有方案....

1. #!/usr/bin/python
   
2. #coding:utf-8
   
3. 
   
4. import itertools
   
5. import re
   
6. from copy import deepcopy
   
7. from collections import Counter
   
8. 
   
9. moneys = {
   
10.     3: 4,
    
11.     4: 6,
    
12.     5: 8,
    
13.     6: 10
    
14. }
    
15. 
    
16. class parsefile(object):
    
17.     def __init__(self, file):
    
18.         self.n = {}
    
19.         self.k = {}
    
20.         with open(file) as fd:
    
21.             for line in fd:
    
22.                 l = re.split(r"[:\s]+\s*", line.rstrip())
    
23.                 d = re.sub(r"^.", "", l[0])
    
24.                 self.n.setdefault(int(d), []).append(l[0])
    
25.                 self.k[l[0]] = l[1:]
    
26. 
    
27.     def get_tcs(self):
    
28.         return self.n.values()
    
29. 
    
30.     def get_kms(self):
    
31.         return self.k
    
32. 
    
33.     def get_tcs_groups(self, seqs):
    
34.         return [ item for item in itertools.product(*seqs)]
    
35. 
    
36.     def moneyfrom(self, seqs):
    
37.         maps = self.get_kms()
    
38.         temp = []
    
39.         for it in seqs: temp.extend(maps[it])
    
40.         d = Counter(temp)
    
41.         t = []
    
42.         for i, v in d.items():
    
43.             if v >= 3:
    
44.                 t.append('%d%s' %(v,i))
    
45.         return '+'.join(t)
    
46. 
    
47.     def getmoneys(self, seqs):
    
48.         maps = self.get_kms()
    
49.         temp = []
    
50.         for it in seqs: temp.extend(maps[it])
    
51.         d = Counter(temp)
    
52.         money = 0
    
53.         for i, v in d.items():
    
54.             if v >= 3:
    
55.                 money += moneys[v]
    
56.         return money
    
57.         
    
58.     def getmaxmoneys(self, seqs):
    
59.         alls = {}
    
60.         max  = 0
    
61.         for it in seqs:
    
62.             rmb = self.getmoneys(it)
    
63.             if rmb > max:
    
64.                 alls = {}
    
65.                 max  = rmb
    
66.                 alls.setdefault(rmb, []).append(it)
    
67.             elif rmb == max:
    
68.                 alls.setdefault(rmb, []).append(it)
    
69.         return alls
    
70. 
    
71.     def rmtcs(self, s, *d):
    
72.         t = [ j for i in d for j in i ]
    
73.         for k, v in enumerate(s):
    
74.             for i in v:
    
75.                 if i in t:
    
76.                     s[k].remove(i)
    
77.         return s
    
78. 
    
79.     def printfmt(self, seq):
    
80.         k = self.get_kms()
    
81.         t = []
    
82.         for i in seq:
    
83.             t.append("%s: %s" %(i, ' '.join(k[i])))
    
84.         return ' '.join(t)
    
85. 
    
86. pp = parsefile('file')
    
87. yy = pp.get_tcs()
    
88. t1 = deepcopy(yy)
    
89. g1 = pp.get_tcs_groups(t1)
    
90. h1 = pp.getmaxmoneys(g1)
    
91. nm = 0
    
92. for m1, v1 in h1.iteritems():
    
93.     for s1 in v1:
    
94.         t1 = deepcopy(yy)
    
95.         t2 = pp.rmtcs(t1, s1)
    
96.         g2 = pp.get_tcs_groups(t2)
    
97.         h2 = pp.getmaxmoneys(g2)
    
98.         for m2, v2 in h2.iteritems():
    
99.             for s2 in v2:
    
100.                 t1 = deepcopy(yy)
     
101.                 t2 = deepcopy(pp.rmtcs(t1, s1))
     
102.                 t3 = pp.rmtcs(t2, s1, s2)
     
103.                 g3 = pp.get_tcs_groups(t3)
     
104.                 h3 = pp.getmaxmoneys(g3)
     
105.                 for m3, v3 in h3.iteritems():
     
106.                     for s3 in v3:
     
107.                         t1 = deepcopy(yy)
     
108.                         t2 = deepcopy(pp.rmtcs(t1, s1))
     
109.                         t3 = deepcopy(pp.rmtcs(t2, s1, s2))
     
110.                         t4 = pp.rmtcs(t3, s1, s2, s3)
     
111.                         g4 = pp.get_tcs_groups(t4)
     
112.                         h4 = pp.getmaxmoneys(g4)
     
113.                         for m4, v4 in h4.iteritems():
     
114.                             for s4 in v4:
     
115.                                 t1 = deepcopy(yy)
     
116.                                 t2 = deepcopy(pp.rmtcs(t1, s1))
     
117.                                 t3 = deepcopy(pp.rmtcs(t2, s1, s2))
     
118.                                 t4 = deepcopy(pp.rmtcs(t3, s1, s2, s3))
     
119.                                 t5 = pp.rmtcs(t3, s1, s2, s3, s4)
     
120.                                 g5 = pp.get_tcs_groups(t5)
     
121.                                 h5 = pp.getmaxmoneys(g5)
     
122.                                 for m5, v5 in h5.iteritems():
     
123.                                     for s5 in v5:
     
124.                                         t1 = deepcopy(yy)
     
125.                                         t2 = deepcopy(pp.rmtcs(t1, s1))
     
126.                                         t3 = deepcopy(pp.rmtcs(t2, s1, s2))
     
127.                                         t4 = deepcopy(pp.rmtcs(t3, s1, s2, s3))
     
128.                                         t5 = deepcopy(pp.rmtcs(t3, s1, s2, s3, s4))
     
129.                                         t6 = pp.rmtcs(t3, s1, s2, s3, s4, s5)
     
130.                                         g6 = pp.get_tcs_groups(t6)
     
131.                                         h6 = pp.getmaxmoneys(g6)
     
132.                                         for m6, v6 in h6.iteritems():
     
133.                                             for s6 in v6:
     
134.                                                 nm += 1
     
135.                                                 print ' %6s ================' % nm
     
136.                                                 print "%s %d=(%s)" %( pp.printfmt(s1), m1, pp.moneyfrom(s1) )
     
137.                                                 print "%s %d=(%s)" %( pp.printfmt(s2), m2, pp.moneyfrom(s2) )
     
138.                                                 print "%s %d=(%s)" %( pp.printfmt(s3), m3, pp.moneyfrom(s3) )
     
139.                                                 print "%s %d=(%s)" %( pp.printfmt(s4), m4, pp.moneyfrom(s4) )
     
140.                                                 print "%s %d=(%s)" %( pp.printfmt(s5), m5, pp.moneyfrom(s5) )
     
141.                                                 print "%s %d=(%s)" %( pp.printfmt(s6), m6, pp.moneyfrom(s6) )
     
142.                                                 print ''        
     
143.                                                 print ''

复制代码

1.       1 ================
   
2. A1: BJ FF PG A2: FG BJ RX F3: BS FG PJ B4: PJ BS BJ F5: FG BJ BS C6: FG SM PJ 20=(4FG+4BJ+3BS+3PJ)
   
3. B1: JG PF PG B2: PF RX SB A3: JG FG SM A4: PF JG SM B5: PG SM FF B6: JG SM PG 20=(3PF+3PG+4SM+4JG)
   
4. C1: JG FG GD C2: BJ JG SB D3: FG JG BS D4: SB BS FG D5: BJ BS SB D6: BJ PF FF 20=(3FG+3BJ+3BS+3SB+3JG)
   
5. D1: PG FG GD E2: SB PF GD E3: JF GD JG C4: JG SB PF E5: MZ SB PF E6: SB FF GD 16=(4GD+3PF+4SB)
   
6. E1: PG PF PJ D2: RX PG JG C3: PG BS FG F4: MZ FG RX A5: PF MZ BS F6: RX SM FG 12=(3FG+3RX+3PG)
   
7. F1: BJ SM PF F2: SB PJ RX B3: BJ BS PG E4: BJ FF PF C5: BS FF BJ A6: SB MZ JF 6=(4BJ)
   
8. 
   
9. 
   
10.       2 ================
    
11. A1: BJ FF PG A2: FG BJ RX F3: BS FG PJ B4: PJ BS BJ F5: FG BJ BS C6: FG SM PJ 20=(4FG+4BJ+3BS+3PJ)
    
12. B1: JG PF PG B2: PF RX SB A3: JG FG SM A4: PF JG SM B5: PG SM FF B6: JG SM PG 20=(3PF+3PG+4SM+4JG)
    
13. C1: JG FG GD C2: BJ JG SB D3: FG JG BS D4: SB BS FG D5: BJ BS SB D6: BJ PF FF 20=(3FG+3BJ+3BS+3SB+3JG)
    
14. D1: PG FG GD E2: SB PF GD E3: JF GD JG C4: JG SB PF E5: MZ SB PF E6: SB FF GD 16=(4GD+3PF+4SB)
    
15. E1: PG PF PJ D2: RX PG JG C3: PG BS FG F4: MZ FG RX C5: BS FF BJ F6: RX SM FG 12=(3FG+3RX+3PG)
    
16. F1: BJ SM PF F2: SB PJ RX B3: BJ BS PG E4: BJ FF PF A5: PF MZ BS A6: SB MZ JF 8=(3BJ+3PF)
    
17. 
    
18. 
    
19.       3 ================
    
20. A1: BJ FF PG A2: FG BJ RX F3: BS FG PJ B4: PJ BS BJ F5: FG BJ BS C6: FG SM PJ 20=(4FG+4BJ+3BS+3PJ)
    
21. B1: JG PF PG B2: PF RX SB A3: JG FG SM A4: PF JG SM B5: PG SM FF B6: JG SM PG 20=(3PF+3PG+4SM+4JG)
    
22. C1: JG FG GD C2: BJ JG SB D3: FG JG BS D4: SB BS FG D5: BJ BS SB D6: BJ PF FF 20=(3FG+3BJ+3BS+3SB+3JG)
    
23. E1: PG PF PJ E2: SB PF GD E3: JF GD JG C4: JG SB PF E5: MZ SB PF E6: SB FF GD 16=(3GD+4PF+4SB)
    
24. D1: PG FG GD D2: RX PG JG C3: PG BS FG F4: MZ FG RX A5: PF MZ BS F6: RX SM FG 14=(4FG+3RX+3PG)
    
25. F1: BJ SM PF F2: SB PJ RX B3: BJ BS PG E4: BJ FF PF C5: BS FF BJ A6: SB MZ JF 6=(4BJ)
    
26. 
    
27. 
    
28. .
    
29. .
    
30. .
    
31. .
    
32. 
    
33.    9214 ================
    
34. F1: BJ SM PF A2: FG BJ RX F3: BS FG PJ B4: PJ BS BJ F5: FG BJ BS C6: FG SM PJ 20=(4FG+4BJ+3BS+3PJ)
    
35. C1: JG FG GD E2: SB PF GD E3: JF GD JG C4: JG SB PF E5: MZ SB PF E6: SB FF GD 20=(4GD+3PF+4SB+3JG)
    
36. B1: JG PF PG D2: RX PG JG A3: JG FG SM F4: MZ FG RX B5: PG SM FF F6: RX SM FG 20=(3RX+3PG+3SM+3FG+3JG)
    
37. A1: BJ FF PG B2: PF RX SB B3: BJ BS PG E4: BJ FF PF C5: BS FF BJ D6: BJ PF FF 18=(5BJ+3PF+4FF)
    
38. D1: PG FG GD F2: SB PJ RX C3: PG BS FG D4: SB BS FG D5: BJ BS SB B6: JG SM PG 16=(3BS+3PG+3FG+3SB)
    
39. E1: PG PF PJ C2: BJ JG SB D3: FG JG BS A4: PF JG SM A5: PF MZ BS A6: SB MZ JF 8=(3PF+3JG)
    
40. 
    
41. 
    
42.    9215 ================
    
43. F1: BJ SM PF A2: FG BJ RX F3: BS FG PJ B4: PJ BS BJ F5: FG BJ BS C6: FG SM PJ 20=(4FG+4BJ+3BS+3PJ)
    
44. C1: JG FG GD E2: SB PF GD E3: JF GD JG C4: JG SB PF E5: MZ SB PF E6: SB FF GD 20=(4GD+3PF+4SB+3JG)
    
45. B1: JG PF PG D2: RX PG JG A3: JG FG SM F4: MZ FG RX B5: PG SM FF F6: RX SM FG 20=(3RX+3PG+3SM+3FG+3JG)
    
46. A1: BJ FF PG C2: BJ JG SB B3: BJ BS PG D4: SB BS FG D5: BJ BS SB B6: JG SM PG 18=(4BJ+3PG+3BS+3SB)
    
47. E1: PG PF PJ B2: PF RX SB C3: PG BS FG E4: BJ FF PF C5: BS FF BJ D6: BJ PF FF 14=(3BJ+4PF+3FF)
    
48. D1: PG FG GD F2: SB PJ RX D3: FG JG BS A4: PF JG SM A5: PF MZ BS A6: SB MZ JF 0=()
    
49. 
    
50. 
    
51.    9216 ================
    
52. F1: BJ SM PF A2: FG BJ RX F3: BS FG PJ B4: PJ BS BJ F5: FG BJ BS C6: FG SM PJ 20=(4FG+4BJ+3BS+3PJ)
    
53. C1: JG FG GD E2: SB PF GD E3: JF GD JG C4: JG SB PF E5: MZ SB PF E6: SB FF GD 20=(4GD+3PF+4SB+3JG)
    
54. B1: JG PF PG D2: RX PG JG A3: JG FG SM F4: MZ FG RX B5: PG SM FF F6: RX SM FG 20=(3RX+3PG+3SM+3FG+3JG)
    
55. A1: BJ FF PG C2: BJ JG SB B3: BJ BS PG D4: SB BS FG D5: BJ BS SB B6: JG SM PG 18=(4BJ+3PG+3BS+3SB)
    
56. E1: PG PF PJ B2: PF RX SB D3: FG JG BS E4: BJ FF PF C5: BS FF BJ D6: BJ PF FF 14=(3BJ+4PF+3FF)
    
57. D1: PG FG GD F2: SB PJ RX C3: PG BS FG A4: PF JG SM A5: PF MZ BS A6: SB MZ JF 0=()

复制代码

bikkuri

谢谢您的程序。
怎么我执行的时候出错。

1. [box@ruizi:~/school]$ ./sort_school2.sh
   
2. Traceback (most recent call last):
   
3.   File "./sort_school2.sh", line 7, in <module>
   
4.     from collections import Counter
   
5. ImportError: cannot import name Counter
   

复制代码

是还需要安装什么组件吗？

回复 28# reyleon


   

bikkuri

非常感谢！

回复 25# ly5066113