SCHeng

It all returns to nothing.

二分查找, 算法与数据结构, 算法题

二分查找Multiset

scheng

题目链接

题目大意:

对一个多重集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<int> 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;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注