自动搬运

查看原文

来自洛谷，原作者为

	Mophie 祈祷着你今后的人生，永远都会有幸福的魔法相伴。

搬运于2025-08-24 22:34:19，当前版本为作者最后更新于2021-11-03 22:12:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

来水一发题解。个人感觉黑题有点虚高。

我们先猜测一下最终状态是什么。

设最终状态是 $a_1, a_2, ..., a_n$，且 $a_1 \le a_2 \le... \le a_n$。

那么很显然，这个状态成立当且仅当：

• 每次能够挑选最小的两个数合并起来，然后每个时刻最小值的两倍均严格大于最大值。

然后呢，就可以得到：

• $a_1+a_2 < 2 \times a_3, a_3 + a_4 < 2 \times a_5$…… 这些限制条件。

所以说必然不能有 $a_1 = a_2 = a_3$ 或者 $a_3 = a_4 = a_5$ 之类的。

相当于说只能满足每个数出现次数 $\le 2$ 或者 $1 + 3$ 的形式。

我们先只考虑全部 $\le 2$ 的情况。

那么假设 $a_n = k$，那么显然 $a_1 > \frac{k}{2}$ 的。

考虑填满后再删去一些数，那么先拿一个 $k = 6$ 手玩一下。发现可以使减少和等于 $0,4,5,6,8,9,10,11.....$

最重要的特点是中间隔的是 $1,2,3,7...$

首先如果上面这样构造能构造的出来的话，必然是最优的且合法的（这个很好证吧）。

然后考虑把 $1+3$ 的情况给塞回去，发现可以通过减少一个最小数，多一个另外的数来达到这个目的。

那么此时就可以除了 $7$ 以外全部处理完了。

最后想想这个 $7$，手推一下可以想到放到下一次弄必然不劣。

那么就把这个 $7$ 放到下面特判即可。

具体细节见代码。

Code：

/*
   长弓背负，仙女月鹫，
   梦中徐来，长夜悠悠。
   今宵共君，夜赏囃子，
   盼君速归，长夜悠悠。
   睡意袭我，眼阖梦徭，
   睡意袭我，意归襁褓。
   手扶卓揭，仙女水狃，
   盼君速归，长夜悠悠。
   今宵共君，戏于西楼，
   盼君速归，长夜悠悠。
   睡意袭我，涟锜池留，
   睡意袭我，意归海角。
					                  ——《ever17》
*/
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	int sum = 0, nega = 1;
	char ch = getchar();
	while (ch > '9'||ch < '0')
	{
	    if (ch == '-') nega = -1;
		ch = getchar();
	}
	while (ch <= '9'&&ch >= '0') sum = sum * 10 + ch - '0', ch = getchar ();
	return sum * nega;
}
const int N = 1e5 + 9;
int n, pep, res;
int cnt[N]; 
queue<int> q;
int ansx[N], ansy[N];
inline int val(int x) {return x * (x + 1) / 2;}
signed main()
{
	n = read();
	for (int i = 1; i <= n; i++)
	{
		int p = i / 2;
		int v = (val(i) - val(p)) * 2;
		p++;
		if(v < n && n - v <= i - p)
		{
			for (int j = p; j <= i; j++) cnt[j] = 2;
			cnt[p]--, cnt[p + n - v]++;
			res = 0;
			for (int j = p; j <= i; j++)
				for (int k = 1; k <= cnt[j]; k++) 
				{
					q.push(j); res += j;
				}
			while(!q.empty())
			{
				int x = q.front(); q.pop(); 
				if(q.empty()) break;
				int y = q.front(); q.pop();
				ansx[++pep] = x + y, ansy[pep] = x;
				q.push(x + y);
			}
			cout << pep << endl;
			for (int j = pep; j >= 1; j--) printf("%lld %lld\n", ansx[j], ansy[j]);
			return 0;
		} 
		if(v >= n && (v - n >= p || v - n == 0))
		{
		//	cout << v << " " << i << endl;
			if(v - n == i + 1 && i % 2 == 0) continue;
			for (int j = p; j <= i; j++) cnt[j] = 2;
			if(v - n == 0) ;
			else if(v - n <= i) cnt[v - n]--;
			else if(v - n <= i + p) cnt[p]--, cnt[v - n - p]--;
			else if(v - n <= i * 2) cnt[i]--, cnt[v - n - i]--;
			else if(v - n <= i * 2 + p) cnt[i]--, cnt[p]--, cnt[v - n - i - p]--;
			else cnt[i]--, cnt[i - 1]--, cnt[p] = 0;
			res = 0;
			for (int j = p; j <= i; j++)
				for (int k = 1; k <= cnt[j]; k++) 
				{
					q.push(j); res += j;
				}
			if(res != n) continue;
			while(!q.empty())
			{
				int x = q.front(); q.pop(); 
				if(q.empty()) break;
				int y = q.front(); q.pop();
				ansx[++pep] = x + y, ansy[pep] = x;
				q.push(x + y);
			}
			cout << pep << endl;
			for (int j = pep; j >= 1; j--) printf("%lld %lld\n", ansx[j], ansy[j]);
			return 0;
		}
	}
	return 0;
}