本文共 1574 字，大约阅读时间需要 5 分钟。

【例题5】给定N(N <= 100000)个编号为1-N的球，将它们乱序丢入一个“神奇的容器”中，作者会在丢的同时询问其中编号第K大的那个球，“神奇的容器”都能够从容作答，并且将那个球给吐出来，然后下次又可以继续往里丟。       现在要你来模拟这个神奇的容器的功能。可以抽象成两种操作：       1. put x                 向容器中放入一个编号为x的球；       2. query K             询问容器中第K大的那个球，并且将那个球从容器中去除（保证K<容器中球的总数）；             这个问题其实就是一维Median Filter的原型了，只是那个问题的K = r+1，而这里的K是用户输入的一个常量。所谓二分模型就是在求和的过程中，利用求和函数的单调性进行二分枚举。

       对于操作1，只是单纯地执行add(x, 1)即可；而对于操作2，我们要看第K大的数满足什么性质，由于这里的数字不会有重复，所以一个显而易见的性质就是一定有K-1个数大于它，假设它的值为x，那么必然满足下面的等式：sum(N) - sum( x ) == K-1，然而，满足这个等式的x可能并不止一个，需要找到最小的那个。

  二分：

                                int t;				while(l <= r){					//printf("l = %d r = %d\n",l,r);					m = (l+r)/2;					if(check(m)){						r = m-1;						t = m; //这里用mid记录最后一个满足条件的位置					}					else{						l = m+1;					}				}

输入：

5 3

put 8put 7put 3put 2query

end

输出：

3

#include
   
    using namespace std;const int N = 100010;int C[N+1];int k,n;int lowBit(int i){	return i&(-i);}int getSum(int i){	int sum = 0;	while(i){		sum += C[i];		i -= lowBit(i);	}	return sum; }int add(int i,int x){	while(i <= N){		C[i] += x;		i += lowBit(i);	}}bool check(int i){	return getSum(N) - getSum(i) <= k-1; }int main()	{	//	freopen("C:/Users/zhangwei/Desktop/input.txt","r",stdin);		char s1[10];		scanf("%d%d",&n,&k);		int x,k = 0;		while(scanf("%s",s1) == 1 && s1[0] != 'e'){			scanf("%d",&x);			if(s1[0] == 'p'){				add(x,1);			}			else if(s1[0] == 'q'){				int l = 1,r = N,m;				int t;				while(l <= r){					//printf("l = %d r = %d\n",l,r);					m = (l+r)/2;					if(check(m)){						r = m-1;						t = m;					}					else{						l = m+1;					}				}				add(t,-1);					printf("第%d次取出的是%d号球\n",++k,t);			} 		}				return 0;		}
   

转载地址：http://veimi.baihongyu.com/