#include #include #include 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; }