# 平方和球柱：出题人解法——保存分层构造

## 最大数量的证明

记 $C(n)=\lfloor(n+1)^2/2\rfloor-1$ .

**上界。** 设已经放入了 $T=C(n)+1=\lfloor(n+1)^2/2\rfloor$ 个球。考察最大的 $n+1$ 个编号，即 $T-n,\ldots,T$ .其中任意两个不同编号之和严格大于 $n^2$ 且严格小于 $(n+1)^2$ ，所以不能相邻。每根柱子的编号从底到顶严格递增，这些大编号在该柱上必然构成连续的顶端部分；若某柱有两个，就会有两个相邻的大编号，产生矛盾。因此需要至少 $n+1$ 根柱子，上界成立。

**达到上界的构造。** 一根柱子只放球一。对于奇数 $n>1$ ，在当前 $n$ 根柱子上放两层，从顶到底描述如下，局部列编号为 $j=0,\ldots,n-1$ ：

$$\text{上层}_j=C(n)-n+1+j,\qquad \text{下层}_j=C(n)-n-j.$$

再在中间 $n-2$ 根柱子的下方递归放入规模 $n-2$ 的方案。上下两层相邻和为 $n^2$ ；第二层与递归部分第一层的相邻和为 $(n-1)^2$ .剩余相邻关系由归纳保证。两层使用最大的 $2n$ 个编号，因为 $C(n)-C(n-2)=2n$ ，所有编号不重不漏。

对于偶数 $n$ ，最上层从左到右为 $C(n),C(n)-1,\ldots,C(n)-n+1$ ，前 $n-1$ 根柱子的下方放规模 $n-1$ 的方案。相接两层的编号和为 $n^2$ ，并且 $C(n)-C(n-1)=n$ .故也合法且恰好用尽一到 $C(n)$ .

所有列从顶到底严格递减，因此逆向按编号从小到大放入，正好遵守原操作时序。构造与上界合起来证明最优数量就是 $C(n)$ .

## 程序组织

为每根柱子准备一个向量，从顶到底记录编号。初始待写编号为 $C(N)$ .偶数规模时，先从左到右为每列写入一个递减的编号，随后只保留前 $N-1$ 列。奇数规模时，先从右到左写入一层，再从左到右写入一层；去掉最外两列后继续。最后中间一列加入球一。

该填充顺序正好实现上面的两层公式。每个编号写入一次，且各列自上而下的先后关系得到保留，最终逐列输出即可。

![An optimal arrangement on four stacks](assets/stacks.svg)

## 复杂度、适用范围与来源

时间为 $O(N^2)$ 次整数操作，存储所有球需要 $O(N^2)$ 空间；按输出字符计需 $O(N^2\log N)$ 时间。[alternative.cpp](alternative.cpp) 可通过完整数据，显式方案也便于检查或供后续处理。首选[按列生成](solution.zh.md)将额外空间降至常数。

出题人解法提供容量公式与分层构造，GPT-6 整理证明、向量实现和独立验证。方案经平方和、唯一性、顺序及数量检查；小规模最大容量另与二分图最大匹配比较。性能见[记录](../../../docs/benchmark-R24.json)。