http://acm.nyist.net/JudgeOnline/problem.php?pid=1261
分析:若是每次都想用sort继而来查第k个数,那会T的特别惨~
C++内置函数upperbound(查找数组的首地址, 查找数组的尾地址, 待查找元素)为logn复杂度的二分查找,
返回第一个比待查找元素大的元素地址。
#include <stdio.h> #include <algorithm> #include <string.h> #include <vector> using namespace std; vector<int>G; int main() { int n, x; char op[5]; while(scanf("%d", &n)!=EOF) { G.clear(); while(n --) { scanf("%s %d", op, &x); if(op[0]=='Q') { int len = G.size(); if(x>len) printf("-1 "); else printf("%d ",G[x-1]); } else { int index = upper_bound(G.begin(), G.end(), x)-G.begin(); G.insert(G.begin()+index, x); } } } return 0; }