Skip to content

1040: The Remains of the Day

题目

题目描述

"Why, Mr Stevens, why, why, why do you always have to pretend?"

The Remains of the Day by Kazuo Ishiguro

相信大家对于 c++ 标准库中的 std::sortstd::nth_element 函数都特别熟悉。他们的函数原型如下:

cpp template<class RandomIt, class Compare> constexpr void sort(RandomIt first, RandomIt last, Compare comp); template<class RandomIt, class Compare> constexpr void nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare comp);

前者用于排序一个可迭代容器。后者用于在可迭代容器中找到关键字排第 $n$ ($0$-base 意义,下同)的元素(时间复杂度线性)。

除了将关键字第 $n$ 的元素放在位置 $n$ 上以外,nth_element 还会将关键字小于该元素的所有元素放在此元素左边的位置上,关键字大于该元素的所有元素放在此元素右边的位置上。但是该元素左右两边元素的内部相对顺序并没有保证。

现在我们希望你实现这两个函数,要求达到相同的时间效率。当然,为了简化问题我们对函数原型做了一定的简化,大家不需要使用模板、迭代器、constexpr 等内容来完成这道题目。

我们保证函数操作的对象是一个 int 数组,且要求通过函数指针而非结构体的方式来传递比较器 comp。形式上和上面给定的函数原型是类似的。

为了考验大家我们当然不能直接给出修改后的函数原型,但是可以展示一段调用函数的示例代码:

```cpp

include

include "example.hpp"

int a[9] = {1, 5, 6, 2, 7, 3, 9, 4, 8};

bool cmp(const int &x, const int &y){return x > y;}

int main() { nth_element(a, a + 8, a + 9, cmp);//find the 8th(0-base) greatest value in a with cmp as comparator std::cout << *(a + 5) << std::endl;// 4 sort(a, a + 9, {return x < y;});//comp is a lambda expression, which returns true if and only if x < y for (int i = 0;i < 9;++ i) std::cout << a[i] << " ";// 1 2 3 4 5 6 7 8 9 std::cout << std::endl; return 0; } ```

请在提交的代码中实现 sortnth_element 两个函数。

~~一句话题意:手写排序和快速选择。~~

输入格式

(无)

输出格式

(无)

样例输入

(无)

样例输出

(无)

数据范围

sort 的正确性占 70 分,nth_element 的正确性占 30 分。

可以添加一些函数或全局变量来辅助执行这两个函数的功能。

不可以调用标准库中的 sortnth_element,甚至其他的有排序功能的标准库容器或者函数。

不要 using namespace std,否则可能会出现函数的重载问题。

不要 向 stdout 输出任何内容。

可以使用任何算法来实现这两个函数,只要它们的时间复杂度分别是 $O(n\log n)$ 和 $O(n)$ 即可。

我们会人工审查每一份提交的代码以进一步确认你满足了上述要求。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!