首页 > 试题广场 >

【入门班】第k大与第m大

[编程题]【入门班】第k大与第m大
  • 热度指数：128 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
\hspace{15pt}本题翻译自 [HDU6231] K-th Number 。其前身为 2017 CCPC中国大学生程序设计竞赛（哈尔滨站）试题。
\hspace{15pt}对于给定的由 n 个元素组成的数组 \{a_1,a_2,\cdots,a_n\} ，你需要按照下方的规则构建一个新的数组 b ：
\hspace{23pt}\bullet\,初始时数组 b 为空；
\hspace{23pt}\bullet\,随后，对于数组 a 中的每一个长度大于等于 k 的区间，找到该区间的第 k 大元素，将这个元素添加到数组 b 中；
\hspace{23pt}\bullet\,重复上述操作，直到数组 a 中所有长度大于等于 k 的区间都被检查完毕；
\hspace{15pt}最后，直接输出数组 b 中的第 m 大元素。

输入描述:
\hspace{15pt}每个测试文件包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 10\right) 代表数据组数，每组测试数据描述如下：

\hspace{15pt}第一行输入三个整数 n,k,m\left(1\leqq n\leqq 10^5;\ 1\leqq k\leqq n;\ 1\leqq m\lt 2^{32}\right) 代表数组 a 中的元素数量、区间限定长度、需要输出的元素在数组 b 中的下标。保证 b_m 存在。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\cdots,a_n\left(1\leqq a_i\leqq 10^9\right) 代表数组 a 中的元素。



输出描述:
\hspace{15pt}对于每组测试数据，在一行上输出一个整数，代表数组 b 中的第 m 大元素。
示例1

输入

6
5 3 1
2 3 1 5 4
5 3 2
2 3 1 5 4
5 3 3
2 3 1 5 4
5 3 4
2 3 1 5 4
5 3 5
2 3 1 5 4
3 3 1
5 8 2

输出

3
3
2
1
1
2

说明

\hspace{15pt}在前五组测试数据中，数组 a 为 \{2,3,1,5,4\} ，长度大于等于 k=3 的区间有：
\hspace{23pt}\bullet\, [1, 3] 排序后得到 \{1, 2, 3\} ;
\hspace{23pt}\bullet\, [2, 4] 排序后得到 \{1, 3, 5\} ;
\hspace{23pt}\bullet\, [3, 5] 排序后得到 \{1, 4, 5\} ;
\hspace{23pt}\bullet\, [1, 4] 排序后得到 \{1, 2, 3, 5\} ;
\hspace{23pt}\bullet\, [2, 5] 排序后得到 \{1, 3, 4, 5\} ;
\hspace{23pt}\bullet\, [1, 5] 排序后得到 \{1, 2, 3, 4, 5\} ;
\hspace{15pt}因此数组 b 即为 \{1, 1, 1, 2, 3, 3\} 。
算法知识视频讲解
开通博客
头像 pamhip
发表于 2020-04-23 19:28:06
题意 有T组数据。每组数据给定长度为 的数组 ，对所有长度大于等于 的连续子段，取出其第 大放入数组 中。求数组 的第 大。 分析 先吐槽一下，第 大表意真的不明啊！！这题简直是套路套路套路题。前几天刚做过类似的。。。考虑二分答案然后检查可行性。（没做过的话真难想啊！！我们不妨设 ，看 展开全文
去ta的博客 赞 (21) 回复(3) 收起
头像 ThinkofBlank
发表于 2020-04-21 12:40:48
Update:添加了一种常数小的做法 一.闲话 看了下大佬们的题解，然后。。。二分+尺取？？？ 我：。。。 二.题解 题目简意: 数组b的元素是，数组a中所有区间长度大于等于k的区间的第k大数(有点绕？) 求数组b中第m大的数 要做这题，首先我们需要明白一个简单的性质，对于一个序列，我们如果添加进一 展开全文
去ta的博客 赞 (10) 回复(0) 收起
头像 19_hanhan
发表于 2020-04-22 16:08:08
这题要我老命。。二分加尺取（见专栏），秀到了大佬，吓到了我。（现学） 题目 题目描述： 给Alice一个带有N个数字的数组A [1...N]。 现在，Alice想通过参数K按照以下规则构建数组B： 最初，数组B为空。考虑数组A中的每个间隔。如果此间隔的长度小于K，则忽略此间隔。否则，在 展开全文
去ta的博客 赞 (9) 回复(4) 收起
头像 shyyhs
发表于 2021-01-08 14:49:14
前言: 为什么他理解的第k大和我们理解的第k大是这样的不同呢?(没看样例前一直在调bug.吐了//) 思路: 二分出来答案,然后检测下区间即可.检测区间用尺取就行.这样是一定符合单调性的. 代码: #include <bits/stdc++.h> using namespace std; 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 与人无语
发表于 2020-04-21 14:18:19
一直没想到二分然后想正解 看了别人说才想到那么这题就简单了 二分答案然后验证check函数为 判断第K大的数大于等于x的区间数面向结果编程..... #include<bits/stdc++.h> #define ll long long using namespace std; 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 Kur1su
发表于 2020-04-21 14:48:29
题意 给一个长度为 的数组 ，把所有长度大于等于 的区间中的第 大值插入 数组中, 问 数组的第 大数是多少 Solution 思路还是挺好想的, 但是实现起来感觉有点难度因为求的是 数组的第 大, 但是 数组是由 数组中得来的那么我们要求的答案肯定是在a数组中出现过啦考虑把a 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Lausaku
发表于 2021-03-29 17:41:59
描述见题面思路：二分一个值x，检验一下原来序列，看有多少个子序列含有多于k个比x大的值，每找到一个就记录，寻找的时候按照尺取的办法，用一个变量来存当前l和r之间含有多少个大于x的值，只要这个数等于k，那么右指针往右的所有数都算进区间作为子序列，最后看一下，是否存在多于m个子区间，其中含有多于k个比x 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 hnust_liuzelin
发表于 2020-04-21 12:07:37
知识点：二分，尺取题意：给定长度为n的数组，求其中所有长度大于k的区间第k大的数中第m大的数。思路：二分答案x，尺取法判断第K大的数大于等于x的区间数，如果该区间数大于等于m，则answer>=x。代码： #include<bits/stdc++.h> #define ll lon 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 一衍一
发表于 2020-04-21 12:09:37
题意:(英语太垃圾,看翻译,然后越看越懵......,唉,读题真心不易)给定数组 然后取其中 大于 的区间,举个例子 可以得到符合的区间有第二个要求是取的得到的符合的区间里面的第 大加入到 ,例如 ,可以得到 ,最后输出 的第 大的元素,题意就这么多.题解:(这题不会,看别人题解看会的,参考的链接: 展开全文
去ta的博客 赞 (2) 回复(4) 收起
头像 一只橘橘猫
发表于 2020-04-21 16:42:57
题意： 解法： 时间复杂度： std： #include <bits/stdc++.h> using namespace std; #define ll long long const int maxn = 100005; ll a[maxn]; ll n,k,m; bool c 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

二分
上传者：牛客301599号
难度：
0条回答 39浏览

热门推荐

通过挑战的用户

查看代码

相关试题

【入门班】第k大与第m大

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号