3664:Election Time

keyword

数列　2分探索　C++

概要

長さN(<5*10^4)の数列A,Bが与えられる。A[i]が上位Kに入っているようなiの中でB[i]が最大であるようなものを求める問題。
A[i]をコピーしてソートし、A[i]が上位Kに入っているかどうかは2分探索で判定すれば良い。時間計算量O(N * log N)、空間計算量O(N)。

#define MAX_N 50002

int N, K;
int as[MAX_N], bs[MAX_N], adv[MAX_N];

int solve(){
    for(int i=0; i<N; i++){
        adv[i] = as[i];
    }
    sort(adv, adv+N, greater<int>());
    int ma = -1, key = -1;
    for(int i=0; i<N; i++){
        if(ma < bs[i] && binary_search(adv,adv+K,as[i],greater<int>())){
            ma = bs[i];
            key = i;
        }
    }
    return key + 1;
}