题意： n（3000）个点的图  q（10^4）次操作  每次操作从原图更改一条边的权值  问q次操作后最小生成树的平均值是多少 思路： 先求最小生成树  然后讨论  如果更改的不是树边  则最小生成树不变  如果是树边  就要选择原图中的非树边和更改后的这条边其中较小的一个形成新树 难做的只有“是树边”这种情况  我们考虑  原图中的非树边与原树一定可以形成一个环  那么我们可以这样理解

//按照降序排列，而且队列中只保存k个元素 #include<stdio.h> #include<queue> using namespace std; int main(){     int n,k;     while(~scanf("%d%d",&n,&k)){         priority_queue<int,vector<int>,greater<i

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4006 求一个数字序列的第K大的值。先输入两个数字n,k,接着是n行输入，I表示加入新的数字，Q是询问第k大的数字。 Sample Input 8 3I 1I 2I 3QI 5QI 4Q Sample Output 123 练习线段树遇到这

本文不想废话，直接上多种做法。 题意：固定的k，动态加点，动态询问第k大数。 一、树状数组+二分 这里有两种做法，一种是二分sum(i)，另一种是利用二进制二分逼近k。 树状数组常用来处理区间点的统计情况，这里n没有规定大小（理论上是int32），但是操作次数n是小于1000,000的，所以可以先进行离散化来储存1000,000个点值（我不知道这是不是所谓的离散化，因为点本身是整数，但是，

题目 C - Travel along the Line ZOJ - 4006 BaoBao is traveling along a line with infinite length.At the beginning of his trip, he is standing at position 0. At the beginning of each second, if he is st