uva 501 Black Box

点击打开链接uva 501

思路: vector模拟
分析:
1 题目的规模是n和m最大为30000，那么明显复杂度要为O(nlogn)级别才能过
2 由于枚举u数组需要n，所以剩下的是logn的时间，明显只有二分可以做到。所以利用vector来模拟，插入的时候利用二分找到位置即可

代码:

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 30010;

int n , m;
int num[MAXN];

void solve(){
    vector<int>v;
    vector<int>::iterator it;
    v.clear();
    int x , pos = 0;
    int index = 0;
    while(m--){
         scanf("%d" , &x);
         while(v.size() != x){
              it = lower_bound(v.begin() , v.end() , num[pos]);
              v.insert(it , num[pos++]);
         }
         printf("%d\n" , v[index++]);
    }
}

int main(){
    int Case;
    bool first = true;
    scanf("%d" , &Case);
    while(Case--){
        scanf("%d%d" , &n , &m);
        if(first)
            first = false;
        else
            puts("");
        for(int i = 0 ; i < n ; i++)
            scanf("%d" , &num[i]);
        solve();
    }
    return 0;
}