【深基9.例4】求第 k 小的数
题目描述
输入 ( 且 为奇数)个数字 (),输出这些数字的第 小的数。最小的数是第 小。
请尽量不要使用 nth_element
来写本题,因为本题的重点在于练习分治算法。
输入格式
输出格式
样例 #1
样例输入 #1
5 1
4 3 2 1 5
样例输出 #1
2
思路
先快速排序,然后通过数组索引访问第k小的数。由于数据过大,需要打开O2优化。
AC代码
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;
const int maxn = 5000005;
int a[maxn];
void read(int &x)
{
char ch;
x = 0;
while (('0' > ch || '9' < ch))
{
ch = getchar();
}
while (!('0' > ch || '9' < ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
}
int *particition(int a[], int *low, int *high)
{
int *l = low, *r = high, pivot = *low;
while (l < r)
{
while (l < r && *r > pivot)
{
r--;
}
while (l < r && *l <= pivot)
{
l++;
}
if (l < r)
{
swap(*(l++), *(r--));
}
}
if (*l > pivot)
{
swap(*(l - 1), *low);
return l - 1;
}
else
{
swap(*l, *low);
return l;
}
}
void quickSort(int a[], int *low, int *high)
{
if (low < high)
{
int *mid = particition(a, low, high);
quickSort(a, low, mid - 1);
quickSort(a, mid + 1, high);
}
}
int main()
{
int n, k;
read(n);
read(k);
for (int i = 0; i < n; i++)
{
read(a[i]);
}
quickSort(a, a, a + n - 1);
/* for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
} */
cout << a[k] << endl;
return 0;
}
标签:P1923,ch,洛谷,int,深基,high,read,while,low
From: https://blog.51cto.com/HEX9CF/8861287