题目：1176：谁考了第k名
题目描述：
在一次考试中，每个学生的成绩都不相同，现知道了每个学生的学号和成绩，求考第k名学生的学号和成绩。
输入：
第一行有两个整数，分别是学生的人数n（1≤n≤100），和求第k名学生的k（1≤k≤n）。
其后有n行数据，每行包括一个学号（整数）和一个成绩（浮点数），中间用一个空格分隔。
输出：
输出第k名学生的学号和成绩，中间用空格分隔。（注：请用%g输出成绩）
时空限制
1s / 64 MB
样例输入：
5 3
90788001 67.8
90788002 90.3
90788003 61
90788004 68.4
90788005 73.9
样例输出：
90788004 68.4
代码1
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,double> PII;
const int N=100+10;
PII a[N];
int n,k;
int quick_sort(int l,int r,int k){
if(l==r) return l;
double x=a[(l+r)/2].second;
int i=l–1,j=r+1;
while(i<j){
do i++;while(a[i].second>x);
do j—;while(a[j].second<x);
if(i<j) swap(a[i],a[j]);
}
int sl=j–l+1;
if(k<=sl) return quick_sort(l,j,k);
return quick_sort(j+1,r,k–sl);
}
int main(){
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++) scanf("%d %lf",&a[i].first,&a[i].second);
int res=quick_sort(0,n–1,k);
printf("%d %g",a[res].first,a[res].second);
return 0;
}
代码2
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,double> PII;
const int N=100+10;
PII a[N];
int n,k;
int quick_sort(int l,int r,int k){
if(l==r) return l;
double x=a[(l+r)/2].second;
int i=l–1,j=r+1;
while(i<j){
while(a[++i].second>x);
while(a[—j].second<x);
if(i<j) swap(a[i],a[j]);
}
int sl=j–l+1;
if(k<=sl) return quick_sort(l,j,k);
return quick_sort(j+1,r,k–sl);
}
int main(){
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++) scanf("%d %lf",&a[i].first,&a[i].second);
int res=quick_sort(0,n–1,k);
printf("%d %g",a[res].first,a[res].second);
return 0;
}
结果
