ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年3月29日 581点热度 1人点赞 0条评论

题目传送门: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: atcoder C++ set
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号