我正在从CodeForces解决this question:
我们给出了三个值,
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
是否,如果(r+g+b)/2
则返回true
,否则返回r+g
。可以说,我不明白社论怎么说。
有人可以指出为什么我逻辑不正确,我缺少什么?
谢谢!
因为您需要找到解决此问题的最佳方法。
例如,1,1,10,最佳方法是r&b,g&b。在您的方法中,结果仅为1。
因此,我们需要对三个值进行排序,并始终使用最大的数字来得出答案。
即使您的解决方案得到纠正,它也可能无法通过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;
}
...