SRM147 DIV2 950

贪心策略的题，解释一下题目的意思

环可以被砍出一个口子用于连接两个链子（脑海里想象一下），现在希望在破坏环最少的情况下将所有的环连成一个圈，很容易想到这种贪心法：

1. 如果当前还剩下1条链子，破坏随便一边的一个环，直接首尾相连

2. 如果当前还剩下2条链子，如果其中一条链子只有一个环，直接用这个环联结另外一条链的首尾，如果都是多环链，只能破坏两个环去相连。

3. 如果当前有2条链子以上，每次选择环数最少的那个链子砍出一个环用于连接环数最大的两条链子，如果这个是一个单环链，那么认为这条链消失。重复过程直到链子数不多于2条。

 1 import unittest
 2 
 3 class GoldenChain:
 4     def minCuts(self, sections):
 5         sections = sorted(sections)
 6         i = len(sections) - 1
 7         j = 0
 8         cnt = 0
 9         while True:
10             if i == j:
11                 cnt += 1
12                 break
13             if i == j + 1:
14                 if sections[j] == 1:
15                     cnt += 1
16                 else:
17                     cnt += 2
18                 break
19             sections[j] -= 1
20             if sections[j] == 0:
21                 j += 1
22             i -= 1
23             cnt += 1
24 
25         return cnt
26 
27 
28 # test 
29 o = GoldenChain()
30 t = unittest.TestCase()
31 
32 
33 # test case
34 t.assertEqual(o.minCuts((3,3,3,3)), 3)
35 t.assertEqual(o.minCuts((2000000000,)), 1)
36 t.assertEqual(o.minCuts((1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,
37 21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,
38 38,39,40,41,42,43,44,45,46,47,48,49,50)), 42)
39 t.assertEqual(o.minCuts((20000000,20000000,2000000000)), 3)
40 t.assertEqual(o.minCuts((10,10,10,10,10,1,1,1,1,1)), 5)
41 t.assertEqual(o.minCuts((1,10)), 1)

View Code