/ Vijos / 题库 / 第k大 /

题解

38 条题解

  • 2
    @ 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();
    }
    
  • 1
    @ 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

  • 1
    @ 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
    readln(n,k);
    for i:=1 to n do
    read(a[i]);
    qsort(1,n);
    write(a[n+1-k])
    end.

    蒟蒻 弱弱压过

  • 0
    @ 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;
    }
    
  • 0
    @ 2016-06-25 23:48:10

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

  • 0
    @ 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;
    }
    ```

  • 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
    readln(n,k);
    for i:=1 to n do readln(a[i]);
    qsort(1,n);
    writeln(a[n-k+1]);
    end.

  • 0
    @ 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;
    }

  • 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;
    }

  • 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
    read(n,k);
    fillchar(hash,sizeof(hash),0);
    min:=maxlongint;
    max:=-1;
    for i:=1 to n do
    begin
    read(t);
    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.

  • 0
    @ 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
    read(n); read(k);
    for i:=1 to n do
    begin
    read(num);
    data[i]:=num;
    end;
    qsort(1,n);
    write(data[n-k+1]);
    end.

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

    program ex;
    var n,num,i,k,max:longint;
    data:array[0..32767] of longint;
    begin
    read(n); read(k);
    max:=0;
    fillchar(data,sizeof(data),0);
    for i:=1 to n do
    begin
    read(num);
    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.

  • 0
    @ 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;
    }

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

    由于每个数最大只有32767,所以可以用计数排序。
    Tip:读入时得用read读入,否则全WA。
    var
    n,k,i,x,max:longint;
    a:array[0..35000] of longint;
    begin
    readln(n,k); max:=0;
    fillchar(a,sizeof(a),0);
    for i:=1 to n do
    begin
    read(x);
    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.

  • 0
    @ 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;
    }

  • 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;
    }

  • 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;
    }
    这都能过

  • 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;
    }

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

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

  • 0
    @ 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
分类
模拟 点击显示
标签
(无)
递交数
2037
已通过
646
通过率
32%
被复制
2
上传者