FoxPaintingBalls

作者：王子健 汪乐平

关键词：分析

题目简述

给定你三种颜色（红、蓝、绿）的小球，其中红色球有$A$个，蓝色球有$B$个，绿色球有$C$个。
你要用这些小球排列成若干满足以下条件的三角形：

$1$.三角形第$n$行要有$n$个小球。

$2$.相邻的小球不能出现相同颜色。

请问最多排列出多少这样的三角形？

$1≤N≤10^9,0≤A,B,C≤10^{18}$

分析

我们不妨先来从上到下画一画满足条件的三角形，看一看这样的三角形有什么性质。
不难发现如果我们确定了前两个小球的颜色，整个三角形也随之而定，因为以后的每个小球都与$2$个已经确定颜色的小球相邻。

进一步观察可得：如果$N\equiv 1(mod\ 3)$，则排列成一个三角形所用的三种小球数总是满足其中一种颜色比另外两种颜色多用$1$个，否则所用三种小球数目相等，且均为$\lfloor \frac{N(N+1)}{6}\rfloor$个。

算法

设最大个数是$x$，$s=\lfloor \frac{N(N+1)}{6}\rfloor$。列出关于$x$的不等式。当$N\equiv 0或2(mod\ 3)$时，关于$x$的不等式有三个：$x\leq \frac{A}{s}$，$x\leq \frac{B}{s}$，$x\leq \frac{C}{s}$，这三个不等式是显然的；当$N\equiv 1(mod\ 3)$时，还需要考虑每个三角形多的一个小球，再加一个不等式$A+B+C-3sx\geq x$，解得$x\leq \frac{A+B+C}{3s+1}$。求最大的同时满足这几组不等式的整数解即可。

时间复杂度为$O(1)$。