浅析 NC207028 第k小数 （快读、排序）

题目链接：

https://ac.nowcoder.com/acm/problem/207028

题面：

给你一个长度为n的序列，求序列中第k小数的多少。

输入描述:
多组输入，第一行读入一个整数T表示有T组数据。
每组数据占两行，第一行为两个整数n，k，表示数列长度和k。
第二行为n个用空格隔开的整数。

输出描述:
对于每组数据，输出它的第k小数是多少。
每组数据之间用空格隔开

input:
2
5 2
1 4 2 3 4
3 3
3 2 1

output:
2
3

分析+代码：

排序题，但是好像手动实现快速排序也不够快，最后我用内置的sort()函数才AC。

// 手动实现的快速排序未AC

#include<iostream>
#include<vector>

using namespace std;

vector<int> ans;
int a[5000005] = {};

inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if (ch == '-')  // 负数情况
			f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		x = (x<<1) + (x<<3) + (ch^48);
		//        x*2 + x*8
		//  相当于   x*10   +  个位数
		ch = getchar();
	}
	return x * f;
}


int partition(int low, int high) {
	
	if (low == high) return a[low];
	
	int pivot = a[low];
	
	while (low < high) {
		
		while (a[high] >= pivot && low < high) {
			high--;
		}
		a[low] = a[high];
		while (a[low] <= pivot && low < high) {
			low++;
		}
		a[high] = a[low];
		
	}
	
	a[low] = pivot;
	return low;
}


void quick_sort(int low, int high) {
	if (low < high) {
		int pivotpos = partition(low, high);
		
		quick_sort(low, pivotpos-1);
		quick_sort(pivotpos+1, high);
	}
	
	
}


int main () {
	int t;
	cin >> t;
	int n, k;
	for (int i = 0; i < t; i++) {
		n = read();
		k = read();
		for (int j = 0; j < n; j++) {
			a[j] = read();
		}
		
		//		cout << " i : " << i << endl;
		//		cout << "before quick_sort a[k] : ";
		//		for (int k = 0; k < n; k++) {
		//			cout << a[k] << "-";
		//		}
		//		cout << endl;
		
		quick_sort(0, n-1);
		
		ans.push_back(a[k-1]);
		
		//		cout << "after quick_sort a[k] : ";
		//		for (int k = 0; k < n; k++) {
		//			cout << a[k] << "-";
		//		}
		//		cout << endl << endl;
	} 
	
	for (auto an : ans) {
		cout << an << endl;
	}
	
}

直接使用sort()函数AC：

#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>

using namespace std;

vector<int> ans;
int a[5000005] = {};

inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if (ch == '-')  // 负数情况
			f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		x = (x<<1) + (x<<3) + (ch^48);
		//        x*2 + x*8
		//  相当于   x*10   +  个位数
		ch = getchar();
	}
	return x * f;
}

int main () {
	int t;
	cin >> t;
	int n, k;
	for (int i = 0; i < t; i++) {
		n = read();
		k = read();
		for (int j = 0; j < n; j++) {
			a[j] = read();
		}
		
		//		cout << " i : " << i << endl;
		//		cout << "before quick_sort a[k] : ";
		//		for (int k = 0; k < n; k++) {
		//			cout << a[k] << "-";
		//		}
		//		cout << endl;
		
		sort(a, a+n);
		// 似乎用快排也不够快，最后只能使用内置排序算法
		
		
		ans.push_back(a[k-1]);
		
		//		cout << "after quick_sort a[k] : ";
		//		for (int k = 0; k < n; k++) {
		//			cout << a[k] << "-";
		//		}
		//		cout << endl << endl;
	} 
	
	for (auto an : ans) {
		cout << an << endl;
	}
	
}

基于字符读取的“快速读入”函数写法学习：

cin慢是有原因的，其实默认的时候，cin与stdin总是保持同步的，也就是说这两种方法可以混用，而不必担心文件指针混乱，同时cout和stdout也一样，两者混用不会输出顺序错乱。正因为这个兼容性的特性，导致cin有许多额外的开销，如何禁用这个特性呢？只需一个语句std::ios::sync_with_stdio(false);，这样就可以取消cin于stdin的同步了。

有的题目需要大规模输入，很多情况用cin超时，用scanf就能过，因为scanf的速度远远快于cin。但是比scanf还要nb的输入是getchar()，这个读入速度极快。

inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if (ch == '-')  // 负数情况
			f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		x = (x<<1) + (x<<3) + (ch^48);
		//        x*2 + x*8
		//  相当于   x*10   +  个位数
		ch = getchar();
	}
	return x * f;
}

手工实现“快读”要注意什么：##

快读也有不适用的时候，例如读入中包含大量无用空格

1 1      1 12
2      3     3
3  2        1
1       5  2

更多拓展：##

探寻C++最快的读取文件的方案 https://byvoid.com/zhs/blog/fast-readfile/