hiho一下第187周《分隔相同整数》题目分析

0
0

《分隔相同整数》题目分析

本题是《分隔相同字符》的加强版。

《分隔相同字符》的题目分析可以看这里。

在《分隔相同字符》中，数组中的每个元素只能是小写字母('a'-'z')。换句话说，值域范围是[1, 26]。

而在本题中，数组中的整数值域是[1, 1000000000]，照搬《分隔相同字符》的做法会超时。

不过《分隔相同字符》中介绍的结论还是成立的：无解的充要条件是某个数字出现次数超过(N+1)/2。

所以贪心算法仍然适用：

1) 预处理A1~AN，生成二元组集合S={(a1, c1), (a2, c2), ... (am, cm)}。表示a1有c1个，a2有c2个……，am有cm个。

2) 找出c值最大的二元组(ai, ci)。如果ci过多，即ci+ci-1 > n，则无解。

3) 依次找出重排后的第一个数、第二个数……第N个数：

3.1) 找出c值最大的二元组(ai, ci)，如果ci恰好满足：ci+ci-1==n。那么当前数字只能选择ai。

3.2) 如果ci+ci-1 < n，找出a值最小的二元组(aj, cj)。如果前一个数字选的不是aj，那么选择aj。

3.3) 如果前一个数字选的就是aj，再找出a值次小的二元组(ak, ck)。选择ak。

不论上述哪种情况，假设最后选择的是(at, ct)，都要ct--。特别的如果ct=0，则要将(at, ct)从S中删除。

所以我们需要设计一种数据结构，对于二元组集合S={(a1, c1), (a2, c2), ... (am, cm)}，支持以下操作(时间复杂度要低)：

1) 找到c值最大的二元组

2) 找到a值最大的二元组

3) 找多a值次大的二元组

4) 对一个二元组(at, ct)进行ct--的操作

5) 删除一个二元组(at, ct)

能支持以上操作的数据结构很多，比如堆、平衡树，上面的操作都能实现O(logN)的复杂度。考虑到C++ STL里的set/map(Java中的TreeSet/TreeMap)内部实现就是平衡树，我们介绍一种利用set/map实现以上操作的方法，非常简单。

可以参考doubleh同学的代码

Tips: 由于set不能修改容器中的元素，所以ct--操作是先删除(at, ct)再添加(at, ct-1)来实现的。

2 answer(s)

0

python编写的代码一直提示RE，求大神指导

def fun_devision(list_n,list_n2,n,dict1,T_F):
    max_n = max(dict1.values())
    max_number = max(dict1,key = dict1.get)
    if 2 *max_n -1 >  n:
        T_F = -1
    elif 2 *max_n -1 == n:
        for _ in range(max_n):
            list_n.remove(max_number)
        for i in range(0,n,2):
            list_n.insert(i,max_number)
        list_n2 += list_n
    else:
        one = list(set(list_n))[0]
        if one != list_n2[-1]:
            list_n2.append(one)  
        else:
            one = list(set(list_n))[1]
            list_n2.append(one)
        dict1[one] -= 1
        n -= 1
        list_n.remove(one)
        list_n2,T_F = fun_devision(list_n,list_n2,n,dict1,T_F)
    return list_n2,T_F
if __name__ == "__main__":
    n = input()
    list_n = list(map(int,raw_input().split()))
    list_n.sort()
    dict1 = {}
    for i in list_n:
        if i in dict1:
            dict1[i] += 1
        else:
            dict1[i] = 1
    list_n2 = ['a']
    T_F =1
    list_n3,T_F1 = fun_devision(list_n,list_n2,n,dict1,T_F)
    if T_F1 == -1:
        print -1
    else:
        list_n3.remove("a")
        list_n3 = map(str,list_n3)
        print " ".join(list_n3)
2

printf("%d%c", x, " \n"[i == n]);

这句真厉害，受益良多

  • 哈哈 解决了输出空格空行这一历史性难题。

  • 添加评论
  • ✖reply

write answer 切换为英文 切换为中文

转发分享

▲