ARC 028 B

今回はこの問題。

arc028.contest.atcoder.jp

プログラミングコンテストにn人が参加しました。順位はすでにわかっています。「上位i人のうちk番目に若い人」をそれぞれのi(k <= i <= n)に対して求めなさい、という問題です。

回答はこんな感じ。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define mod 1000000007
     
    int main()
    {
        int n, k;
        cin >> n >> k;
        int x[100001];
        for(int i = 0; i < n; i++){
            cin >> x[i];
        }
        priority_queue<pair<int, int> > qu;
        for(int i = 0; i < k; i++){
            qu.push(make_pair(x[i], i + 1));
        }
        priority_queue<pair<int, int> > qu2;
        qu2.push(make_pair(-(qu.top()).first, (qu.top()).second));
        qu.pop();
        for(int i = 0; i < n - k + 1; i++){
            cout << (qu2.top()).second << endl;
            int next = x[i + k];
            // cout << next << endl;
            qu.push(make_pair(next, i + k + 1));
            qu2.push(make_pair(-(qu.top()).first, (qu.top()).second));
            qu.pop();
        }
        return 0;
    }

上位k - 1人について、先頭に最も年をとっている人とその番号が来るようにした優先度つきキューquと、のこりの人について、先頭に最も若い人とその番号がくるようにした優先度つきキューqu2を用意します。最初、quに上位k人についての情報をプッシュしてから、先頭に出てくる情報、つまり上位k人のうちk番目に若い人をqu2にプッシュし、quからポップします。
あとは順番に一人ずつ加えていきます。i + k番目の人をくわえることを考えます。まず、quに次に追加する人の情報をプッシュします。quに含まれている人のうち最も年をとっている人の情報が先頭に来るので、これをqu2に詰め直し、quからポップします。そうすると、qu2の先頭には上位i + k人のうちk番目に若い人がくる、というわけです。優先度つきキューでは最も値の大きいものが出てくるので、qu2ではマイナスをつけることで最も値が小さいものを取り出せるようにしています。