Sweet问题-首先进行排序的直觉

问题描述 投票:3回答:2

我正在从CodeForces解决this question

我们给出了三个值,rgb,分别代表三堆中红色,绿色和蓝色糖果的数量。 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 108 2 8上中断。我的代码分别返回78,而不是109(我不确定109是输入的预期答案)。 editorial讨论有关对输入进行排序并检查b <= r + g是否,如果(r+g+b)/2则返回true,否则返回r+g。可以说,我不明白社论怎么说。

有人可以指出为什么逻辑不正确,我缺少什么?

谢谢!

c++ algorithm logic
2个回答
1
投票

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

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

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


0
投票

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

首先,对3输入数字进行排序。之所以要这样做,是因为我们需要根据它们之间的相对值来选择一对数字。现在,在排序之后,让我们考虑a,b,c: a<=b<=c的可能情况:

0。如果a0(或a,ba,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。如何到那?好吧,只要将ca减一,只要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;
}

...
© www.soinside.com 2019 - 2024. All rights reserved.