#1133 : 二分·二分查找之k小数
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在上一回里我们知道Nettle在玩《艦これ》，Nettle的镇守府有很多船位，但船位再多也是有限的。Nettle通过捞船又出了一艘稀有的船，但是已有的N(1≤N≤1,000,000)个船位都已经有船了。所以Nettle不得不把其中一艘船拆掉来让位给新的船。Nettle思考了很久，决定随机选择一个k，然后拆掉稀有度第k小的船。 已知每一艘船都有自己的稀有度，Nettle现在把所有船的稀有度值告诉你，希望你能帮他找出目标船。
输入
第1行：2个整数N,k。N表示数组长度，
第2行：N个整数，表示a[1..N]，保证不会出现重复的数，1≤a[i]≤2,000,000,000。
输出
第1行：一个整数t，表示t在数组中是第k小的数，若K不在数组中，输出-1。
- 样例输入
-
10 4
1732 4176 2602 6176 1303 6207 3125 1 1011 6600 - 样例输出
-
1732
题目链接：hihoCoder 1133
题目求的是第K小，即从小到大排序后正着数第K个数
例子：1 3 5 三个数中第3大是1，第3小是5，因此第K小用最大堆，第K大用最小堆，这个算法以前看了很久，由于堆不会写就完全看不懂，这次回来把它实现了一下，这份代码支持有重复出现的数的情况。
用堆求TOP K问题的简单步骤（堆的根记为Root）：
1、将无序数据的前K个读入并插入空堆中。
2、继续从K+1个数据开始读入，若某个数据的关键字逻辑上比Root要小，则把Root用这个数据替换，一般情况下直接赋值给Root，然后向下调整堆，为什么？若这个数据比Root要小，则说明整个数组从小到大排序后这个数据的位置肯定在替换Root的前面，因此替换前的Root在读入这个数据后一定会被挤出前K个数之外，因此要替换掉
3、这样处理完N个数后所求的第K大/小就是最后留下的堆的根（代码中储存堆用顺序表且有效下标从1开始）
代码：
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 1000010;
class Maxm_Heap
{
private:
int A[N];
int sz;
public:
void init()
{
sz = 0;
}
void up(const int &cur)
{
int fa = cur >> 1;
if (fa > 0 && A[cur] > A[fa])
{
swap(A[cur], A[fa]);
up(fa);
}
}
void down(const int &cur)
{
int lson = cur << 1;
int rson = lson | 1;
if (lson > sz)
return ;
int son;
if (rson > sz)
son = lson;
else
son = A[lson] > A[rson] ? lson : rson;
if (A[son] > A[cur])
{
swap(A[son], A[cur]);
down(son);
}
}
void push(const int &val)
{
A[++sz] = val;
up(sz);
}
void pop()
{
swap(A[1], A[sz]);
--sz;
down(1);
}
int top()
{
return A[1];
}
void alt_top(const int &val)
{
A[1] = val;
}
};
Maxm_Heap heap; int main(void)
{
int n, k, i;
while (~scanf("%d%d", &n, &k))
{
heap.init();
int val;
for (i = 1; i <= k; ++i)
{
scanf("%d", &val);
heap.push(val);
}
for (i = k + 1; i <= n; ++i)
{
scanf("%d", &val);
if (val < heap.top())
{
heap.alt_top(val);
heap.down(1);
}
}
printf("%d\n", (k < 1 || k > n) ? -1 : heap.top());
}
return 0;
}