首页 > 代码库 > 第K大数

第K大数

2024-07-13 00:18:21   224人阅读

控制数据箱（box.c/cpp/pas）
【题目大意】
现在给你一个数据箱，支持以下操作，加入元素，第 n
次查询操作求当前情况下的第 n 大数。比如说，第 3 次查
询操作求第三小的数。当然查询操作的给出方式有些特
殊，只是给出一个数字，表示在加入第几个元素后进行查
询。
【输入数据】
第一行，n，m
第二行n 个数，表示需要依次插入的数
第三行m 个数，表示在插入第几个数后进行操作
【输出数据】
对于每个操作，输出答案
【输入样例】
7 4
3 1 4 2 8 1000 2
1 2 3 7

【输出样例】

3
3
4
3【数据范围】
对于 30%的数据，1<=n<=10000, 1<=m<=100
对于100%的数据， 1<=n<=200000, 1<=m<=10000

---------------------------

m<=10000!!!!!!

插入排序不错^ ^  不过标算是两个堆，平衡树什么的还是不会啊。YM说数据太弱了插入排序都可以。。。。

var  a,rn,rm:array[1..200001]of longint;  i,n,m,en,st,k,now:longint;procedure cha(x:longint);var next,j:longint;begin  if i>m then next:=m+1 else next:=i;  a[next]:=x;  for j:=next-1 downto 1 do    if x<a[j] then      begin        a[j+1]:=a[j];        a[j]:=x;      end    else break;end;begin  assign(input,‘box.in‘);  assign(output,‘box.out‘);  reset(input);  rewrite(output);  read(n,m);  for i:=1 to n do read(rn[i]);  for i:=1 to m do read(rm[i]);  st:=1;  for k:=1 to m do    begin      st:=en+1;      en:=rm[k];      for i:=st to en do cha(rn[i]);      writeln(a[k]);    end;  close(input);  close(output);end.
View Code


联系
我们