[ABC234]D – Prefix K-th Max(set)

发布于 2022-03-29  694 次阅读


题目传送门: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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-09