语文题，不解释！

测试数据 #0: Accepted, time = 0 ms, mem = 1212 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1212 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1212 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1220 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1216 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1216 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 1212 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 1212 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 1216 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 1212 KiB, score = 10

写的随机快速选择，由于强迫症没用直接的快排....
基本思想就是快排的时候判断一下排在左边的数有多少，然后根据数量得出第K大在哪一边，直接递归哪一边就可以了...

program quickselect;
var n,k,i:longint;
a:array[1..100100]of longint;
function qselect(l,r,k:longint):longint;
var i,j,x,y,p:longint;
begin
if l>r then exit(-1);
i:=l+1;j:=r;
p:=random(r-l)+l;
y:=a[p];a[p]:=a[l];a[l]:=y;
x:=a[l];
repeat
while a[i]<x do inc(i);
while a[j]>x do dec(j);
if i<=j then
begin
y:=a[i];a[i]:=a[j];a[j]:=y;
inc(i);dec(j);
end;
until i>j;
if j-l=k-1 then exit(x);
if j-l>k-1 then exit(qselect(l+1,j,k))
else exit(qselect(j+1,r,k-j+l-1));
end;

begin
randomize;
read(n,k);
for i:=1 to n do read(a[i]);
write(qselect(1,n,n-k+1));
end.

水坑题一道
数据读入必须用read
readln全灭
不知原因

弱爆

记录信息
评测状态 Accepted
题目 P1788 第k大
递交时间 2013-11-06 18:25:26
代码语言 C++
评测机 VijosEx
消耗时间 201 ms
消耗内存 864 KiB
评测时间 2013-11-06 18:25:28
评测结果

编译成功

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

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

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

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

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

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

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

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

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

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

Accepted, time = 201 ms, mem = 864 KiB, score = 100
代码

#include <stdio.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <cstdlib>

using namespace std;

int n , k;
int a[100000 + 10];
int i;

template <class T>
T* qsort(T* a,int l,int r)
{
int i=l,j=r;
T x=a[(l+r)/2];
do{
while(a[i]>x)i++;
while(a[j]<x)j--;
if(i<=j)
{
swap(a[i],a[j]);
i++; j--;
}
}while(i<=j);
if(i<r)qsort(a,i,r);
if(l<j)qsort(a,l,j);
return a;
}

int main()
{
while( scanf( "%d %d" , &n , &k ) != EOF )
{
memset( a , 0 , sizeof( a ) );
for( i = 0 ; i < n ; i++ )
scanf( "%d" , &a[i] );
qsort( a , 0 , n );
cout << a[k - 1] << endl;
}
return 0;
}

这题n简直太小了、至少得10^9

var a:array[1..maxint] of longint;
i,z,n,k,sum:longint;
begin
readln(n,k);
fillchar(a,sizeof(a),0);
for i:=1 to n do
begin
read(z);
inc(a[z]);
end;
for i:=maxint downto 1 do
begin
sum:=sum+a[i];
if sum>=k then break;
end;
write(i);
end.

var
n,i,j,k:longint;
a:array[0..100000]of longint;
procedure sort(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]>x do
inc(i);
while x>a[j] do
dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
begin
readln(n,k);
for i:=1 to n do read(a[i]);
sort(1,n);
writeln(a[k]);
end.
尼玛 必须要READ啊 这什么垃圾题目啊

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

阴人的垃圾题，要用read 和 write还不一定A

var
a:array[1..100000]of longint;
n,k,b:longint;
procedure sort(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]>x do
inc(i);
while x>a[j] do
dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;

begin
readln(n,k);
for b:=1 to n do
read(a[b]); //这个地方如果用了readln 必然是错误答案，我也不知道为什么。
sort(1,n);
write(a[k]);
end.

(╯‵□′)╯︵┻━┻ 看成第k小了 WA了两次= =

#include <stdio.h>

int kth( short int arr[], int length, int k )
{
int nlarger, nsmaller, nequal;
int i;
int temp;
short int * larr;
short int * sarr;
int value;
nlarger=0;
nsmaller=0;
nequal=0;

temp=arr[0];
larr=malloc(length*sizeof(short int));
sarr=malloc(length*sizeof(short int));

for(i=0;i<length;i++)
{
if(arr[i]>temp)
{
larr[nlarger]=arr[i];
nlarger++;
}
else if(arr[i]<temp)
{
sarr[nsmaller]=arr[i];
nsmaller++;
}
else
{
nequal++;
}
}

if(nlarger+nequal<k)
{
value=kth(sarr, nsmaller, k-(nlarger+nequal));
}
else if((nsmaller+nequal)<=(length-k))
{
value = kth(larr, nlarger, k);
}
else
{
value=temp;
}
free(larr);
free(sarr);

return value;
}

int main()
{
int n, k;
short int * table;
int i;
scanf("%d %d", &n, &k);
if(n%2==1)
{
n++;
table = malloc(sizeof(short int)*n);
table[n-1]=0;
for(i=0;i<n-1;i++)
scanf("%d", &table[i]);
}
else
{
table = malloc(sizeof(short int)*n);
for(i=0;i<n;i++)
scanf("%d", &table[i]);
}
i=kth(table, n, k);
printf("%d\n", i);
free(table);
return 0;
}

#include<stdio.h>
#include<stdlib.h>
int main()
{
int a[100000],i,n,k,b;
scanf("%d %d",&n,&k);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<=n;i++)
{
if (a[k]>a[n]);
b=k;
n=b;
k=n;

}
printf("%d",a[k]);
system("pause");
return 0;

}

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int n=0,k=0;
cin>>n>>k;
vector<int> vec;
for(int i=0;i<n;++i){
int grade=0;
cin>>grade;
vec.push_back(grade);
}

sort(vec.begin(),vec.end());

cout<<vec[n-k];
return 0;
}

好水。。。。
```c

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

#include<iostream>
#include<cstring>
#include<cstdio>
#define lson l,m,k<<1
#define rson m+1,r,k<<1|1
#define lrk int l,int r,int k
using namespace std;
const int INF=1<<29;
const int L=400005;
int a[L],pos[L],n,r;

void pushup(int k)
{
    if (a[k<<1]<a[k<<1|1])
    {
        a[k]=a[k<<1];
        pos[k]=pos[k<<1];
    }
    else
    {
        a[k]=a[k<<1|1];
        pos[k]=pos[k<<1|1];
    }
}
int tot=1;
void build(lrk)
{
    if (l==r)
    {
        scanf("%d",&a[k]);
        pos[k]=tot++;
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(k);
}
void update(lrk,int p)
{
    if (l==r)
    {
        a[k]=INF;
        return;
    }
    int m=(l+r)>>1;
    if (p<=m) update(lson,p);
    else update(rson,p);
    pushup(k);
}
int main()
{
    scanf("%d%d",&n,&r);
    build(1,n,1);
    for (int s=0;s<n-r;s++) update(1,n,1,pos[1]);
    printf("%d",a[1]);
}

线段树23333

真·water
计数排序有明显的优越性

var a:array[0 .. 40000] of longint;
n,i,k,b:longint;
begin
read(n,k);
fillchar(a,sizeof(a),0);
for i := 1 to n do
begin
read(b);
inc(a[b]);
end;
b := 0;
for i := 32767 downto 0 do
begin
if b+a[i] >= k then
begin
write(i);
exit;
end else inc(b,a[i]);
end;
end.


#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
struct Node
{
    int x;
    friend bool operator < (Node a, Node b)
    {
        return a.x > b.x;
    }

};
int main()
{
    int n, k;
    priority_queue <Node> q;
    int mark_k = 0;
    scanf("%d%d", &n, &k);

    for(int i = 1; i <= n; i++)
    {
        if(mark_k < k)
        {
            Node num;
            mark_k++;
            scanf("%d", &num.x);
            q.push(num);
        }
        else
        {
            Node num;
            scanf("%d", &num.x);

            if(num.x > q.top().x)
            {
                q.pop();
                q.push(num);
            }
        }
    }

    printf("%d", q.top().x);
    return 0;
}

是不是很无聊

水题
氵氵氵
随便AC
#include<iostream>
#include<algorithm>
using namespace std;
int n,k;
int score[100001];
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
cin>>score[i];
sort(score,score+n,greater<int>());
k--;
cout<<score[k];
return 0;
}