二分查找Multiset

题目链接

题目大意:

对一个多重集a[n],进行k次操作.如果k[i]<0那么从a[n]中删除第k[i]个数据.如果k[i]>0,那么就把k[i]放到多重集a[n]中.如果最后a[n]空了就输出0,否则输出多重集中随机的一个数据.

算法分析:

使用二分查找算法来解决.建立一个函数count_item(x),在多重集中搜索对于x在进行所有k[i]操作后多重集剩余的小于x的数据的数量.

从一个极大的右端点开始搜索,如果都能满足就向左缩小,不能满足就向右扩张,直到整个收缩到多重集中某一合适的值.

#include <bits/stdc++.h>

using namespace std;

int n, q;
vector a, k;

int count_item( int x )
{
int count = 0;
for ( auto iter : a ) if ( iter <= x ) count ++;
for ( auto iter : k )
{
if ( iter > 0 && iter <= x ) count ++;
if ( iter < 0 && abs(iter) <= count ) count –;
//
}
return count;
}

int main()
{

scanf("%d %d", &n, &q);
a.resize(n );
k.resize(q );
for ( int i = 0; i < n; i ++ ) scanf("%d", &a\[i\]);
for ( int i = 0; i < q; i ++ ) scanf("%d", &k\[i\]);
//for ( auto y : a ) printf("%d ", y);
if ( !count\_item((int) 1e9)  ) { printf("0\\n"); return 0; }
int left = 0; int right = int(1e6) + 1;

while ( right - left > 1 )
{
    int mid = ( right + left ) / 2;
    if ( count\_item(mid) ) right = mid;
    else left = mid; 
}
printf("%d\\n",right);

return 0;

}