/ Vijos / 讨论 / 第k大 /

二分查找,不明白90分。

Var
        n,m,i,ans:longint;
        a:array[1..10000]of longint;

Function ef(left,right:longint):longint;
Var
        i,j,mid,t:longint;
Begin
        i:=left; j:=right; mid:=a[(left+right) div 2];
        t:=a[i]; a[i]:=mid; a[(left+right) div 2]:=t;
        repeat
                while (i<j) and (a[j]<=mid) do dec(j);
                if i<j then
                begin
                        t:=a[i]; a[i]:=a[j]; a[j]:=t;
                        inc(i);
                end;
                while (i<j) and (a[i]>=mid) do inc(i);
                if i<j then
                begin
                        t:=a[j]; a[j]:=a[i]; a[i]:=t;
                        dec(j);
                end;
        until i>=j;
        if i<m then exit(ef(i,right));
        if i>m then exit(ef(1,i));
        exit(a[i]);
End;

Begin
        readln(n,m);
        for i:=1 to n do
                readln(a[i]);
        ans:=ef(1,n);
        writeln(ans);
        readln;
End.

1 条评论

  • 1

信息

ID
1788
难度
5
分类
模拟 点击显示
标签
(无)
递交数
2005
已通过
637
通过率
32%
被复制
1
上传者