题解：P11555 [ROIR 2016 Day 2] 三子问题

FZY_CZY · 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 的分类讨论。

最后一种情况就是 n \bmod 3=2，我们与第二种情况一样，也是在 n \bmod 3=0 的情况下，考虑多余的 2 放在哪里，然后就可以再分类（反正 a 是不能加的）。
- 我们来比较一下 (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;
}
```

完结撒花！！！

题解：P11555 [ROIR 2016 Day 2] 三子问题

题意

思路

代码