自动搬运

查看原文

来自洛谷，原作者为

	FZY_CZY 对于人生而言，重要的不是凯旋，而是奋斗

搬运于2025-08-24 23:08:21，当前版本为作者最后更新于2025-01-10 19:45:36，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

题目

简单阐述一下题意：给定一个 $n$，求 $a,b,c$，条件：$a+b+c=n,a < b < c$，并且使得 $a^2+b^2+c^2$ 最小。

思路

举个例子：当 $n=6$ 时，$a=1,b=2,c=3$ 是合法的；当 $n=12$ 时，$a=3,b=4,c=5$ 是合法的。

那么我们就可以猜想：当 $n \bmod 3=0$ 的时候，合法的答案是 $a=\frac{n}{3}-1,b=\frac{n}{3},c=\frac{n}{3}+1$。

我们可以用反证法来证明一下： 假设答案中 $a$ 比我们的 $\frac{n}{3}$ 大 $x$，同理，设出另外的 $y,z$，明显地 $x+y+z=0$，这个时候我们来看一下这种情况下合法的答案。

我们猜想的答案等于 $\frac{n^2}{9}-\frac{2\times n}{3}+1+\frac{n^2}{9}+\frac{n^2}{9}+\frac{2\times n}{3}+1$，整理得 $\frac{n^2}{3}+2$。

然后我们来看一下我们假设合法的答案等于 $\frac{n^2}{9}-\frac{2\times n}{3}+1+x^2+\frac{2\times n\times x}{3}-2\times x+\frac{n^2}{9}+\frac{2\times n\times y}{3}+y^2+\frac{n^2}{9}+\frac{2\times n}{3}+1+z^2+2\times z+\frac{2\times n\times z}{3}$，整理得 $\frac{n^2}{3}+\frac{2\times n\times(x+y+z)}{3}+x^2+y^2+z^2+2\times (z-x)+2$。

这两个式子相减（后面减前面），得到了 $\frac{2\times n\times(x+y+z)}{3}+x^2+y^2+z^2+2\times (z-x)$，现在，我们需要来判断这个式子的正负性，结合我们的 $x+y+z=0$，这个式子经过操作后一定是非负的，那么我们的猜想是正确的，这个式子一定是最小的，那么 $a,b,c$ 一定是合法的。

然后我们可以看，$a<b<c$，那么我们结合之前的理论，$b$ 在一般情况下是 $\frac{n}{3}$，那么，我们就很自然的想到用 $\frac{n}{3}$ 作为一个衡量的标准，然后就是对于 $n \bmod 3$ 的分类讨论。

1. $n\bmod 3=0$，那么显然，$a=\frac{n}{3}-1,b=\frac{n}{3},c=\frac{n}{3}+1$。
2. $n\bmod 3=1$，根据我们的结论，得出 $a=\frac{n}{3}-1,b=\frac{n}{3},c=\frac{n}{3}+2$，因为在第一种情况的基础上剩余的 $1$ 只能放在 $c$ 上，否则就会有 $a=b$，明显不合法。
3. 最后一种情况就是 $n \bmod 3=2$，我们与第二种情况一样，也是在 $n \bmod 3=0$ 的情况下，考虑多余的 $2$ 放在哪里，然后就可以再分类（反正 $a$ 是不能加的）。

• $b+1,c+1$，就有 $a^2+(b+1)^2+(c+1)^2=a^2+b^2+2\times b+1+c^2+2\times c+1$。
• $c+2$，就有 $a^2+b^2+(c+2)^2=a^2+b^2+c^2+4\times c+4$。
• 我们来比较一下 $(a^2+(b+1)^2+(c+1)^2=a^2+b^2+2\times b+1+c^2+2\times c+10)$ 和 $(a^2+b^2+(c+2)^2=a^2+b^2+c^2+4\times c+4)$ 的大小，考虑到 $b<c,2<4$ 所以将 $2$ 拆开，分别加到 $b$ 和 $c$ 上面更加符合题意的 $\min$。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
int a,b,c;
int main(){
	cin>>n;
	a=n/3-1,b=n/3,c=n/3+1;
	if (n%3==2) b+=1;
	if (n%3!=0) c+=1;
	cout<<a<<" "<<b<<" "<<c;
	return 0;
}

完结撒花！！！