题目传送门:D - Prefix K-th Max (atcoder.jp)
题目大意
给定一个大小为N的排列,从第K个数字开始,每次求从开始到该数字为止的序列中的第K大的数字。
思路
如果是一个月前,我将会不知所措。但是最近atcoder出了好几个multiset和set的题目,于是不难想到用set这个神奇的数据结构。
因为set的插入和查询复杂度均为O(logN),所以可以很轻松地完成这道题。

代码
#include <bits/stdc++.h> #define int long long using namespace std; signed main() { int N, K;cin >> N >> K; set<int> s; for(int i = 1, x;i <= N; ++ i) { cin >> x;s.insert(x); if(s.size() > K)s.erase(s.begin()); if(s.size() == K)printf("%lld\n",*s.begin()); } return 0; }
Comments NOTHING