https://scg3.piaoztsdy.cn/p/271
考虑使用快速排序，对于一个区间 ：
- 如果区间长度不大于 ，直接返回。
- 随机选取一项 作为参考值，其中 代指下标。
- 将 冒泡排序到 处。
- 将 冒泡排序到 处，记录每一项和它交换时花费的金币数：
- 和小于 的项交换会花费 个金币。
- 和大于 的项交换会花费 个金币。
- 将除 以外的项就地交换，使得大于 的项都位于小于 的项的右边。
- 交换 和最靠左的大于 的项。
- 递归处理 和 。
实践表明，这一算法平均只需要花费大约 枚金币，且 次测试下最多只需要花费 枚金币。
#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
random_device seed;
mt19937 rd;
const int N = 1000 + 12, Real_N = 1000;
int t[N];
void deal(int l, int r)
{
if (l >= r) return;
int p = l + rd() % (r - l + 1);
for (int i = p; i >= l + 1; i--)
operate(i - 1, i);
for (int i = l; i <= r - 1; i++)
t[i] = operate(i, i + 1);
queue <int> q;
for (int i = r - 1; i >= l; i--)
{
if (t[i] == 2)
if (!q.empty())
{
operate(i, q.front());
swap(t[i], t[q.front()]);
q.pop();
}
if (t[i] == 1) q.push(i);
}
p = r;
for (int i = l; i <= r - 1; i++)
if (t[i] == 2)
{
operate(i, r);
p = i;
break;
}
deal(l, p - 1);
deal(p + 1, r);
}
int main()
{
rd.seed(seed());
deal(1, Real_N);
confirm();
return 0;
}
暂无评论