You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
60 lines
1.1 KiB
60 lines
1.1 KiB
#include <iostream>
|
|
#include <algorithm>
|
|
#include <cstring>
|
|
using namespace std;
|
|
const int N = 1025;
|
|
|
|
//快读
|
|
int read() {
|
|
int x = 0, f = 1;
|
|
char ch = getchar();
|
|
while (ch < '0' || ch > '9') {
|
|
if (ch == '-') f = -1;
|
|
ch = getchar();
|
|
}
|
|
while (ch >= '0' && ch <= '9') {
|
|
x = (x << 3) + (x << 1) + (ch ^ 48);
|
|
ch = getchar();
|
|
}
|
|
return x * f;
|
|
}
|
|
|
|
//树状数组
|
|
int tr[N];
|
|
void add(int x, int c) {
|
|
for (; x < N; x += x & -x) tr[x] += c;
|
|
}
|
|
//查询x的个数和
|
|
int getSum(int x) {
|
|
int sum = 0;
|
|
for (; x; x -= x & -x) sum += tr[x];
|
|
return sum;
|
|
}
|
|
|
|
//从1开始查找第k小的数
|
|
int getKth(int k) {
|
|
int l = 1, r = N - 1; //保证数组不能越界
|
|
while (l < r) {
|
|
int mid = (l + r) >> 1;
|
|
if (getSum(mid) >= k)
|
|
r = mid;
|
|
else
|
|
l = mid + 1;
|
|
}
|
|
return l;
|
|
}
|
|
/*
|
|
测试用用例:
|
|
2 9 1 3 12 7 6 -1
|
|
3
|
|
|
|
答案：
|
|
3
|
|
*/
|
|
int main() {
|
|
int x;
|
|
while (x = read(), ~x) add(x, 1); // x这个位置上+1
|
|
int k = read();
|
|
printf("%d\n", getKth(k));
|
|
return 0;
|
|
} |