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

_second_coming_ · 2025-01-10 21:00:26 · 题解

洛谷P11555 [ROIR 2016 Day 2] 三子问题

球管理给过 TwT

传送门

依题意可知，我们有一个数 n ，并且 a+b+c=n，并且使 a^2+b^2+c^2 最小。
推理一下，可知 a,b,c 尽量接近，a^2+b^2+c^2 才能最小。

推理过程

1. 设定条件：考虑 a + b + c = k（k 为某个常数）。

2. 应用均值不等式：
   根据均值不等式，我们有：

   \frac{a^2 + b^2 + c^2}{3} \geq \left( \frac{a + b + c}{3} \right)^2

   将 a + b + c = k 代入，可以得到：

   \frac{a^2 + b^2 + c^2}{3} \geq \left( \frac{k}{3} \right)^2

   因此：

   a^2 + b^2 + c^2 \geq \frac{k^2}{3}

3. 等号条件：
   上述不等式的等号成立当且仅当 a = b = c。即当 a, b, c 相等时，a^2 + b^2 + c^2 达到最小值。

4. 所得结论：
   因此，我们可以得出结论：当 a + b + c 一定时，a^2 + b^2 + c^2 最小值 \frac{k^2}{3} 当且仅当 a = b = c 的时候实现。因此，a, b, c 尽量接近时，a^2 + b^2 + c^2 将达到其最小值。

综上所述，通过均值不等式，我们证明了当 a + b + c 取定值时，a^2 + b^2 + c^2 取得最小值时，a, b, c 必须尽量接近（即相等）。这个结论对任何相似的问题同样适用。

那怎么使 a,b,c 最接近呢？
可以从 n\bmod3 的值入手。 （一定要注意题目中说 a<b<c！）

• 如果 x\bmod3=0，显然 a=\dfrac{n}{3}-1,b =\dfrac{n}{3},c=\dfrac{n}{3}+1 是最优解。
• 如果 x\bmod3=1，这个 1 显然不能加在 a,b 上，不然就会有 a=b 或 b=c 的情况出现，因此只能 a=\dfrac{n}{3}-1,b =\dfrac{n}{3},c=\dfrac{n}{3}+2。
• 如果 x\bmod3=2，（这是本篇题解和楼上唯一不同的地方！）可以看作 x\bmod3=3 也就是 x\bmod3=0 中一个数减了一，这个 1 显然不能减在 b,c 上，不然也会有 a=b 或 b=c 的情况出现，因此只能 a=\dfrac{n}{3}-1,b =\dfrac{n}{3}+1,c=\dfrac{n}{3}+2。

  code

  综上所述，代码：

  #include<bits/stdc++.h>
  using namespace std;
  int main(){
  int n;
  cin>>n;
  if(n%3==0)
      printf("%d %d %d",n/3-1,n/3,n/3+1);
  else if(n%3==1)
      printf("%d %d %d",n/3-1,n/3,n/3+2);
  else
      printf("%d %d %d",n/3-1,n/3+1,n/3+2);
  }