P1923 【深基9.例4】求第 k 小的数

Rayna ·

更新时间:2024-11-11

· 692 次阅读

菜鸡如我在这道题知道了原来输入以可以超时，所以这个时候就需要快读这种神奇的东西。

还有nth_element和sort排序小能手。

题目描述
输入 n(n<5000000且 n 为奇数) 个数字 ai(0<ai<10^9)，输出这些数字的第 k 小的数。最小的数是第 0 小。

输入格式
无

输出格式
无

输入输出样例
输入
5 1
4 3 2 1 5
输出
2

超时代码1（基础版）：

#pragma GCC optimize(3,"Ofast","inline")
#include
using namespace std;
int main(){
    int n,num;
	cin>>n>>num;
	int cor[n];
	for(int i=0;i>cor[i];
	}
	for(int i=0;i<n;i++){
		for(int j=i+1;jcor[j]){
				swap(cor[i],cor[j]);
			}
		}
	}
	cout<<cor[num];
	return 0;
}

超时代码2（nth_element版）：

#pragma GCC optimize(3,"Ofast","inline")
#include
using namespace std;
int main(){
    int n,num;
	cin>>n>>num;
	int cor[n];
	for(int i=0;i>cor[i];
	}
	nth_element(cor,cor+num,cor+n);
	cout<<cor[num];
	return 0;
}

超时代码2（sort版）：

#pragma GCC optimize(3,"Ofast","inline")
#include
using namespace std;
int main(){
    int n,num;
	cin>>n>>num;
	int cor[n];
	for(int i=0;i>cor[i];
	}
	for(int i=0;i<n;i++){
		for(int j=i+1;jcor[j]){
				swap(cor[i],cor[j]);
			}
		}
	}
	sort(cor,cor+n);
	cout<<cor[num];
	return 0;
}

哈哈哈不知道还有多少人翻到这里，不多BB，奉上AC代码（nth_element和sort都可以，问题在输入）：

#pragma GCC optimize(3,"Ofast","inline")
#include
using namespace std;
inline int read();
int main(){
    int n,num;
	cin>>n>>num;
	int cor[n];
	for(int i=0;i<n;i++){
		cor[i]=read();
	}
	nth_element(cor,cor+num,cor+n);
	//sort(cor,cor+n);
	cout<<cor[num];
	return 0;
}
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    } 
    return x*f;
}

作者：bupt_sanqing

1024 个赞