考虑使用快速排序，对于一个区间 $[l, r]$：

1. 如果区间长度不大于 $1$，直接返回。
2. 随机选取一项 $p$ 作为参考值，其中 $p$ 代指下标。
3. 将 $p$ 冒泡排序到 $l$ 处。
4. 将 $p$ 冒泡排序到 $r$ 处，记录每一项和它交换时花费的金币数：
   • $p$ 和小于 $p$ 的项交换会花费 $1$ 个金币。
   • $p$ 和大于 $p$ 的项交换会花费 $2$ 个金币。
5. 将除 $p$ 以外的项就地交换，使得大于 $p$ 的项都位于小于 $p$ 的项的右边。
6. 交换 $p$ 和最靠左的大于 $p$ 的项。
7. 递归处理 $[l, p - 1]$ 和 $[p + 1, r]$。

实践表明，这一算法平均只需要花费大约 $3 \times 10^4$ 枚金币，且 $10^4$ 次测试下最多只需要花费 $42156$ 枚金币。

#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;
}