SRM 594 DIV 2

枚举题，由于 (A) 和 (B) 是原数的比例，将原题重新叙述为：

已知集合 (A) 和 (B)，(k_1A) 和 (k_2B) 是 (A)、(B) 分别乘以 (k_1)、(k_2) 的数组。找到一组 ((k_1, k_2)) 使得 (k_1A) 和 (k_2B) 中不相同的数尽可能少，找到这个最小的数

(k_1, k_2) 无上限，不可能枚举所有的 (k_1, k_2)

最优情况下必然存在数 ((a, b) in (A, B)) 使得 (k_1a=k_2b)，或者不存在则最优解直接为 (len(A)+len(B))。

可令 ((k_1, k_2)=(b, a))，这是一组符合条件可能导出最优解的组合，因此算法如下：

枚举所有的 ((a, b) in (A, B))，计算 ({bA+aB}) 中不同数的个数，取最小值。

现在的问题是，这样的枚举算法是否囊括了所有情况，或者至少囊括所有最优解的情况？

只需证明：

((k_1, k_2)=(pb, pa) (pb,pa in N^*)求得的结果相同 )

于是，(k_1a=k_2b) 情况下只需取任意一组合法的 ((k_1, k_2)) 求解即可

 1 from fractions import gcd
 2 
 3 class AstronomicalRecordsEasy:
 4     def minimalPlanets(self, a, b):
 5         result = len(a) + len(b)
 6         for x in a:
 7             for y in b:
 8                 aa = [t*y for t in a]
 9                 bb = [t*x for t in b]
10                 s = set(aa + bb)
11                 result = min(result, len(s))
12         return result
13 
14 
15 # test
16 o = AstronomicalRecordsEasy()
17 
18 # test case
19 assert(o.minimalPlanets((1,2,3,4), (2,3,4,5)) == 5)
20 assert(o.minimalPlanets((1,2,3,4), (2,4,6,8)) == 4)
21 assert(o.minimalPlanets((1,2,3,5,6,8,9), (2,4,5,6,7,8,9)) == 9)
22 assert(o.minimalPlanets((1,2,3,4), (6,7,8,9)) == 6)
23 assert(o.minimalPlanets((200,500), (100,200,300,400,600,700,800,900)) == 9)
24 assert(o.minimalPlanets((1,2,3,4,5,6,7,8,9,10,11,12), (6,7,8,9,10,11,12,13,14,15)) == 15)
25 print('ok')

View Code