现在的位置: 首页 > 综合 > 正文

【模拟】找第k小的数

2013年01月03日 ⁄ 综合 ⁄ 共 1199字 ⁄ 字号小中大 ⁄ 评论关闭

题目:找第k小的数 rqnoj350

题目描述

给出一个长度为N的序列A1,A2,A3,...,AN，其中每项都是
小于10^5的自然数。
现在有M个询问，每个询问都是Ai...Aj中第k小的数等
于多少。
数据范围：
在60%的数据中，1≤N≤1000，1≤M≤1000
在100%的数据中，1≤N≤10000,1≤M≤2000

Darkmaster说：“这题水吧？水了就得给我AC了看看，呵呵！”

输入格式

第一行两个正整数N，M。
第二行N个数，表示序列A1,A2,...,AN。
紧着的M行，每行三个正整数i,j,k(k≤j-i+1)，表示
询问Ai...Aj中第k小的数等于多少。

输出格式

共输出M行，第i行输出第i个询问的答案。

样例输入

4 3 4 1 2 3 1 3 1 2 4 3 1 4 4

样例输出

1 3 4

Pascal Code

program rqnoj350;

var
  n,m:longint;
  a,b:array[0..200000+10] of longint;

procedure init;
begin
  assign(input,'rqnoj350.in');
  assign(output,'rqnoj350.out');
  reset(input);
  rewrite(output);
end;
procedure outit;
begin
  close(input);
  close(output);
  halt;
end;

procedure readdata;
begin
end;

procedure swap(var a,b:longint);
var t:longint;
begin
  t:=a;a:=b;b:=t;
end;

procedure qsort(l,r:longint);
var
  i,j:longint;
  x:longint;
begin
  i:=l;j:=r;x:=a[(i+j)div 2];
  repeat
    while a[i]<x do inc(i);
    while a[j]>x do dec(j);
    if i<=j then
    begin
      swap(a[i],a[j]);
      swap(b[i],b[j]);
      inc(i);dec(j);
    end;
  until i>j;
  if i<r then qsort(i,r);
  if l<j then qsort(l,j);
end;

procedure main;
var
  i,j,x,y,k,num:longint;
begin
  read(n,m);
  for i:=1 to n do
  begin
    read(a[i]);
    b[i]:=i;
  end;
  qsort(1,n);
  for i:=1 to m do
  begin
    read(x,y,k);
    num:=0;
    for j:=1 to n do
    begin
      if (b[j]<x)or(b[j]>y) then continue;
      inc(num);
      if num=k then
      begin
        writeln(a[j]);
        break;
      end;
    end;
  end;
end;


begin
  init;
  readdata;
  main;
  outit;
end.