给定3个正整数，求最大步数将其降为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;
}

Answer 1

即使您的解决方案得到了纠正，它也可能无法通过对codeforces的所有测试，因为它的时间复杂度与输入数字的值成正比。但是，存在一个解，它的运行时间与输入数无关。

首先，对3输入数字进行排序。如果它们没有排序，那么在每次迭代中，我们将需要找到最大和最小元素，然后递减它们。如果这些数字是排序的，那么我们马上就知道最大和最小的数字在哪里，所以我们可以立即递减它们。

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

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;
}

...