分成两步来做:
1.首先进行预处理,构造数组E
E--所有包含集合X中第i个元素的S[j]的集合,1引用2楼ThirstyCrow的回复:分成两步来做:
1.首先进行预处理,构造数组E
E--所有包含集合X中第i个元素的S[j]的集合,1
貌似我也想到过这个方法。
第二步,我觉得在第一次选择了集合S[t]以后,所有其他集合中的和S[t]重合的元素就要删掉(否则每次选取最大是不对的)。这样每选择了一个集合以后,其他集合大小就变了,也就是下一次选的时候要重新遍历所有集合。这样得到的复杂度为O(∑|S|+|C|(2|F|-|C|+1)/2)
复杂度的后半截是因为,每次选择模最大的集合S都要遍历剩余的所有集合,总的时间付出为|F|+|F|-1+...+|F|-|C|+1
下面举个特例,X={1,2,...,n},F={{1},{2},...,{n}}
这样|C|(2|F|-|C|+1)/2=n(n-1)/2,而∑|S|=n
|