给定三个正整数，找到将它们减少为0的最大步数。

Question

我正在解决 CodeForces 上的这个问题:

我们有三个值，r、g 和 b，它们分别表示三堆糖果中红色、绿色和蓝色糖果的数量。Tanya 一天不能吃两颗相同颜色的糖果，即，她每天只能吃两颗不同颜色的糖果。找到 Tanya 最多可以吃糖果的天数。

我用以下简单的方法解决了它:

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，如果为true则返回(r+g+b)/2，否则返回r+g。可以说，我无法理解这篇文章在说什么。

请问有人能指出我的逻辑有什么问题，我错过了什么吗？

谢谢！

- user8386434

Answer 1

因为您需要找到此问题的最佳方法。

例如，1,1,10，最佳方式是r＆b，g＆b。在您的方法中，结果仅为1。

因此，我们需要对三个值进行排序，并始终使用最大的数字来达到答案。

- 2997ms

Answer 2

即使您的解决方案已经被更正，也可能无法通过codeforces上的所有测试，因为其时间复杂度与输入数字的值成比例。但是存在一种解决方案，其运行时间是恒定的，不受输入数字的影响。

首先，对3个输入数字进行排序。如果它们没有排序，则在每次迭代中我们都需要找到最大和最小元素，然后将它们递减。如果数字已排序，则我们立即知道最大和最小数字的位置，因此我们可以立即将它们递减。

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

0.如果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;
}

...

- Anatolii