Skip to content

1248: 最优排序

题目

题目描述

请注意,本题为非传统题,你不应该期望在此题得到满分,根据你做法的优劣你将得到不超过 100 的一个分值。本题只支持 C++ 语言,不保证使用其他语言能通过编译。

有 $n$ 个编号分别为 $0, 1, \cdots n - 1$ 的球。这 $n$ 个球的大小两两不同。你每次可以比较两个球的大小关系,你需要调用尽量少次比较将它们排序。

你需要在程序的第一行 #include "sort.hpp"。你不应该实现 main 函数,你只需要实现一个函数: c++ std::vector<int> my_sort(int n) 它接受球的个数 ,返回球按大小从小到大排列后的编号顺序。你可以调用一个函数: c++ bool query(int a, int b) 如果球 $a$ 比球 $b$ 轻,该函数会返回 $1$,否则返回 $0$ 。

输入格式

输出格式

样例输入

样例输出

数据范围

本题共 1 个测试点,$n = 10^3$。

在这个测试点中,你的 my_sort 函数会被调用恰好 $10$ 次。每次球的大小均匀独立随机生成且两两不同。

若你没有正确地将球按大小排序,你得到 $0$ 分。

否则设你一共调用了 $p$ 次 query,若 $p > 10^8$ 你会得到 $0$ 分,否则设 $q = 10\lceil \log_2 (n!)\rceil = 85300$,你的得分为 $$\lceil 10\sum_{i=0}^{10} (\frac{q}{p})^i\rceil$$

请不要恶意攻击交互库(包括但不限于查看交互库源码并生成相同的排列、读取内存)。

一个可以获得分数的程序:

```c++

include "sort.hpp"

std::vector my_sort(int n) { std::vector v; for(int i=0;i<n;++i) v.push_back(i); for (int i = 0; i < n; i++) for (int j = i - 1; j >= 0; j--) if (query(v[j + 1], v[j])) { int t = v[j]; v[j] = v[j + 1]; v[j + 1] = t; } return v; } ```

Oops! 本题目还没有解答!

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

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

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