A题在算出若干个N所对应的颜色个数后就能发现模式了。

当有N行时,至少需要每种颜色

重点是当n%3==1的情况,我们需要解决一个小小的线性规划问题(可以二分):
设(R,G,B)可以涂成m组,则必有min(R,G,B)/x>=m,并且R+G+B-3xm>=m,可以二分解决。

class FoxPaintingBalls
{
    public:
        long long theMax(long long R, long long G, long long B, int N)
        {
            if (N == 1) return R + G + B; /// 特判
         ll x = ((ll) N * (N + 1) / 2) / 3;
            if (N % 3 == 0 || N % 3 == 2) return min(R, min(G, B)) / x;
            ll l = -1LL, r = R + G + B + 1LL, m;
            while (l + 1LL < r)
            {
                m = (l + r) >> 1LL;
                if (min(R, min(G, B)) / x >= m && R + G + B - 3LL * x * m >= m) l = m;
                else r = m;
            }
            return l;
        }
};

Comments

comments powered by Disqus