poj.2985.The k-th Largest Group
Newman likes playing with cats. He possesses lots of cats in his home. Because the number of cats is really huge, Newman wants to group some of the cats. To do that, he first offers a number to each of the cat (1, 2, 3, …, n). Then he occasionally combines the group cat i is in and the group cat j is in, thus creating a new group. On top of that, Newman wants to know the size of the k-th biggest group at any time. So, being a friend of Newman, can you help him?
要点:
- 1.统计每一个Group的大小
- 2.所有的Group的大小组成的集合,求集合的第K大元素
树状数组
树状数组中寻找第K大元素
二分法
2985.The k-th Largest Group.cpp