c++ - 给定 3 个正整数，找到将它们减少到 0 的最大步数

Question

我正在解决this question来自 CodeForces:

We are given three values, r, g and b which represent number of Red, Green and Blue candies in three piles, respectively. Tanya can't eat two candies of the same color in a day i.e., each day she eats exactly two candies of different colors. Find the maximal number of days Tanya can eat candies.

我用以下简单的方式做到了:

int main() {
    int t, r, g, b;
    cin>>t;

    while(t--) {
        int counter=0;
        cin >> r >> g >> b;

        while(r && g) {
            r--;
            g--;
            counter++;
        }

        while(g && b) {
            g--;
            b--;
            counter++;
        }

        while(r && b) {
            r--;
            b--;
            counter++;
        }

        cout<<counter<<"\n";
    }

    return 0;
}

但是，它在输入 7 4 10 时中断和8 2 8 。我的代码返回 7和8分别代替 10和9 (我不确定 10 和 9 是输入的预期答案)。 editorial讨论对输入进行排序并检查是否 b <= r + g并返回(r+g+b)/2如果true和r+g否则。可以说，我无法理解社论所说的内容。

有人可以指出为什么我的逻辑不正确以及我错过了什么吗？

谢谢!

Answer 1

即使您的解决方案得到纠正，它也可能无法通过 codeforces 上的所有测试，因为其时间复杂度与输入数字的值成正比。但存在一种解决方案，无论输入数字如何，其运行时间都是恒定的。

首先，排序3输入数字。如果它们没有排序，那么在每次迭代中我们需要找到最大和最小元素，然后递减它们。如果数字已排序，那么我们立即知道最大和最小的数字在哪里，因此我们可以立即递减它们。

现在，排序后让我们考虑 a,b,c: a<=b<=c 的可能情况:

0.if a是 0 (或 a,b 或 a,b,c )那么数字显然是 min(b,c) 。

1.对于a, b, c: b = c, a > 0递减 a,b 总是更好然后a,c依次产生最大迭代次数。例如，2,3,3 -> 1,2,3 -> 0,2,2 -> 0,1,1 -> 0,0,0 。如果a = c and b = c然后它仍然true -2,2,2 -> 1,1,2 -> 0,1,1 -> 0,0,0 .

2.对于a, b, c: a != b and b != c我们应该记住大小写 1最大化迭代次数。到那里怎么走？好吧，通过递减 c和a只要 a变成0 (那么不需要 1 ，因为我们已经可以将剩余步骤计算为 min(b, c - a) )或 c等于 b然后是案例1 。如果我们尝试减少任何其他数字对，那么迭代次数将减少为 b将无缘无故地减少:)。之后我们就可以申请案例1 。

3.此方法可以在 O(1) 中实现时间复杂度。

...    

int main() {
    int t;
    std::cin >> t;

    for (int i = 0; i < t; i++) {
        std::vector<int32_t> array(3);
        for (int32_t& value : array) {
            std::cin >> value;
        }
        std::sort(array.begin(), array.end());
        int32_t days = 0;

        int32_t diff = array[2] - array[1];
        days += (std::min(array[0], diff));
        array[0] -= days;
        array[2] -= days;

        array[2] -= array[0] / 2;
        days += (array[0] / 2);

        array[1] -= array[0] / 2;
        days += (array[0] / 2);

        days += std::min(array[1], array[2]);

        std::cout << days << std::endl;
    }

    return 0;
}

...