/ Vijos / 题库 / 第k大 /

# 38 条题解

• @ 2020-10-15 14:51:53
``````#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

namespace dts
{
int cmp(int x,int y)
{
return x>y;
}

int n,m,a[100000];

void main()
{
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++)
scanf("%d",&a[i]);
sort(&a[0],&a[n],cmp);
printf("%d\n",a[m-1]);
}
}

int main()
{
dts::main();
}
``````
• @ 2020-10-15 14:52:12

H2O

• @ 2017-10-10 21:23:28
``````#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
int a[n];
for (int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
cout<<a[n-k];
return 0;
``````

H2O

• @ 2013-03-10 13:08:54

var
a:array[1..100000]of integer;
n,k,i:longint;
procedure qsort(l,r:longint);
var
i,j,t,x:longint;
begin
i:=l;
j:=r;
x:=a[(l+r)shr 1];
repeat
while a[i]<x do inc(i);
while a[j]>x do dec(j);
if i<=j then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;{O(nlog(n))}
{===========main==========}
begin
for i:=1 to n do
qsort(1,n);
write(a[n+1-k])
end.

蒟蒻 弱弱压过

• @ 2021-07-16 09:39:21

二分法
（来源NOIP2008普及组，完善程序）

``````#include <iostream>
using namespace std;
int a[1000001],n,ans =-1;
void swap(int &a,int &b){
int c;
c=a;a=b;b=c;
}
int FindKth(int left, int right, int n){
int tmp,value,i,j;
if (left==right) return left;
tmp=rand()%(right-left)+left;
swap(a[tmp],a[left]);
value=a[left];
i=left;
j=right;
while (i<j){
while (i<j && a[j]<value) j--;
if (i<j) {a[i]=a[j]; i++;} else break;
while (i<j && a[i]>value) i++;
if (i<j) {a[j]=a[i]; j--;} else break;
}
a[i]=value;
if (i<n) return FindKth(i+1,right,n);
if (i>n) return FindKth(left,i-1,n);
return i;
}
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
ans=FindKth(1,n,k);
cout<<a[ans];
return 0;
}
``````
• @ 2016-06-25 23:48:10

莫名地看成第K小的数了，WA了几发

• @ 2016-05-20 13:38:53

评测结果
编译成功
```c++
测试数据 #0: Accepted, time = 31 ms, mem = 940 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 940 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 936 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 940 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 940 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 940 KiB, score = 10
测试数据 #6: Accepted, time = 46 ms, mem = 940 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 940 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 940 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 936 KiB, score = 10
Accepted, time = 169 ms, mem = 940 KiB, score = 100
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n,k,a[100001];
scanf("%d %d",&n,&k);
for(int i = 1;i <= n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1,greater<int>());
printf("%d",a[k]);
return 0;
}

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 1288 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1284 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1284 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1284 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1284 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1284 KiB, score = 10
测试数据 #6: Accepted, time = 46 ms, mem = 1284 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 1284 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 1284 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 1280 KiB, score = 10
Accepted, time = 169 ms, mem = 1288 KiB, score = 100
代码
#include <cstdio>
int a[100001],b[100001],n,K;
void qsort(int L,int R) {
if (L >= R) return;
int mid = (L+R)/2;
qsort(L,mid);
qsort(mid+1,R);
for (int i = L;i <= R;i++) b[i] = a[i];
int i = L,j = mid+1;
for (int k = L;k <= R;k++)
if (i <= mid && (j > R || b[i] > b[j]))
a[k] = b[i++];
else
a[k] = b[j++];
}
int main() {
scanf("%d %d",&n,&K);
for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
qsort(1,n);
printf("%d",a[K]);
return 0;
}
```

• @ 2016-03-26 20:19:59

var
n,k,i:longint;
a:array[1..10000] of longint;
procedure qsort(l,r:longint);
var
i,j,mid,p:longint;
begin
i:=l;
j:=r;
mid:=a[(l+r) div 2];
repeat
while a[i]<mid do inc(i);
while a[j]>mid do dec(j);
if i<=j then begin
p:=a[i]; a[i]:=a[j]; a[j]:=p;
inc(i); dec(j);
end;
until i>j;
if j>l then qsort(l,j);
if i<r then qsort(i,r);
end;
begin
for i:=1 to n do readln(a[i]);
qsort(1,n);
writeln(a[n-k+1]);
end.

• @ 2015-10-19 19:54:30

记录信息
评测状态 Accepted
题目 P1788 第k大
递交时间 2015-10-19 19:54:14
代码语言 C++
评测机 VijosEx
消耗时间 117 ms
消耗内存 916 KiB
评测时间 2015-10-19 19:54:16
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 916 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 916 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 916 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 916 KiB, score = 10
测试数据 #4: Accepted, time = 10 ms, mem = 916 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 916 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 912 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 912 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 916 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 912 KiB, score = 10
Accepted, time = 117 ms, mem = 916 KiB, score = 100
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
int a[100010];
using namespace std;
int main()
{
int n,k;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
printf("%d",a[n-k+1]);
return 0;
}

• @ 2015-08-05 20:37:10

简单排序
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
long long n,m,a[1100000];
scanf("%I64d%I64d",&n,&m);
for (int i=0;i<n;i++) scanf("%d",&a[i]);
sort(a,a+n);
printf("%I64d\n",a[n-m]);
return 0;
}

• @ 2015-01-14 12:15:14

基数排序

### Pascal Code

var
hash:array[0..32767] of longint;
n,k,i,t,sum,max,min:longint;
begin
fillchar(hash,sizeof(hash),0);
min:=maxlongint;
max:=-1;
for i:=1 to n do
begin
inc(hash[t]);
if t>max then max:=t;
if t<min then min:=t;
end;
sum:=0;
for i:=max downto min do
begin
inc(sum,hash[i]);
if sum>=k then begin writeln(i);break;end;
end;
end.

• @ 2014-12-20 12:42:07

快排：
program ex;
var i,num,j,n,k:longint;
data:array[1..100000] of longint;
procedure qsort(l,r:longint);
var i,x,y,mid,a:longint;
begin
x:=l;y:=r; mid:=data[(l+r) div 2];
repeat
while data[x]<mid do
inc(x);
while data[y]>mid do
dec(y);
if x<=y then
begin
a:=data[x]; data[x]:=data[y]; data[y]:=a; inc(x); dec(y);
end;
until x>y;
if x<r then qsort(x,r);
if l<y then qsort(l,y);
end;
begin //main
for i:=1 to n do
begin
data[i]:=num;
end;
qsort(1,n);
write(data[n-k+1]);
end.

• @ 2014-12-18 20:30:37

program ex;
var n,num,i,k,max:longint;
data:array[0..32767] of longint;
begin
max:=0;
fillchar(data,sizeof(data),0);
for i:=1 to n do
begin
inc(data[num]);
if num>max then
max:=num;
end;

for i:=max downto 1 do
begin
if data[i]<>0 then
k:=k-data[i];
if k<=0 then
begin
write(i);
break;
end;
end;

end.

• @ 2014-12-14 11:30:47

stl秒杀
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
long n,i,k,a[1000000];
cin>>n>>k;
for (i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
cout<<a[n-k];
return 0;
}

• @ 2014-08-02 13:38:28

由于每个数最大只有32767，所以可以用计数排序。
var
n,k,i,x,max:longint;
a:array[0..35000] of longint;
begin
fillchar(a,sizeof(a),0);
for i:=1 to n do
begin
inc(a[x]);
if x>max then max:=x;
end;
i:=max;
while k>0 do
begin
if a[i]=0 then begin dec(i); continue; end;
dec(a[i]); dec(k);
end;
writeln(i);
end.

• @ 2014-06-07 22:08:04

###code
#include<iostream>
#include <algorithm>
int data[1000000];
using namespace std;
int main()
{int k=0;
int n=0;
cin>>n>>k;
for(int i=0;i!=n;++i)
cin>>data[i];
sort(data,data+n);
cout<<data[n-k];
return 0;
}

• @ 2014-06-07 22:07:25

#code
#include<iostream>
#include <algorithm>
int data[1000000];
using namespace std;
int main()
{int k=0;
int n=0;
cin>>n>>k;
for(int i=0;i!=n;++i)
cin>>data[i];
sort(data,data+n);
cout<<data[n-k];
return 0;
}

• @ 2014-06-07 22:07:13

这数据水的可以......
#code
#include<iostream>
#include <algorithm>
int data[1000000];
using namespace std;
int main()
{int k=0;
int n=0;
cin>>n>>k;
for(int i=0;i!=n;++i)
cin>>data[i];
sort(data,data+n);
cout<<data[n-k];
return 0;
}
这都能过

• @ 2014-01-24 11:41:06

系统快排水过,第k大就是第n+1-k小,下标从0开始就是n-k

#include<stdio.h>
#include<cstdlib>
#include<algorithm>
//#include<iostream>
#define N 100000
using namespace std;
int a[N];
int main()

{
int i,k,n;
scanf("%d%d",&n,&k); k = n-k;
for (i = 0;i < n;i++) scanf("%d",a+i);
sort(a,a+n); printf("%d",a[k]);
return 0;
}

• @ 2014-01-01 12:02:39

Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步

• @ 2013-12-02 22:28:03

记录信息
评测状态 Accepted
题目 P1788 第k大
递交时间 2013-11-27 22:54:18
代码语言 C
评测机 VijosEx
消耗时间 124 ms
消耗内存 760 KiB
评测时间 2013-11-27 22:54:19

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 448 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 448 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 448 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 448 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 444 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 448 KiB, score = 10

测试数据 #6: Accepted, time = 31 ms, mem = 760 KiB, score = 10

测试数据 #7: Accepted, time = 31 ms, mem = 724 KiB, score = 10

测试数据 #8: Accepted, time = 31 ms, mem = 744 KiB, score = 10

测试数据 #9: Accepted, time = 31 ms, mem = 716 KiB, score = 10

Accepted, time = 124 ms, mem = 760 KiB, score = 100

代码
#include <stdio.h>
#include <stdlib.h>
int cmp (const void *a,const void *b)
{return *(int )b-(int *)a;
}
int main (){
int n,k,i;
scanf ("%d%d",&n,&k);
int a[n];
for (i=0;i<n;i++)
{scanf ("%d",&a[i]);
}
qsort (a,n,sizeof(a[0]),cmp);
printf ("%d\n",a[k-1]);
return 0;
}

ID
1788

5

(无)

2034

644

32%

2