音痴又音痴的LT

时间:2022-07-29 22:49:59

音痴又音痴的LT

中文题不解释。比赛时想着操作一次sort一次,然而T到死。后来才知道C++内置容器vector这么强大。

内置函数upperbound(查找数组的首地址, 查找数组的尾地址, 待查找元素)为logn复杂度的二分查找,

返回第一个比待查找元素大的元素地址。

附AC代码:

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
vector<int>G;
int main()
{
int n;
while(scanf("%d", &n)!=EOF)
{
G.clear();
char order[];
int k;
for(int i=; i<=n; i++)
{
scanf("%s %d", order, &k);
if(order[]=='Q')
{
int len = G.size();
if(k>len)printf("-1\n");
else printf("%d\n", G[k-]);///vector内部下标从0开始
}
else
{
int index = upper_bound(G.begin(), G.end(), k)-G.begin();///插入位置
G.insert(G.begin()+index, k);
}
}
}
return ;
}