几天前,我试图解决一个 CodeForces 的问题:
有三堆石头,比如A、B和C。我们可以从A中取出1块石头,然后从B中取出2块;或者 1 来自 B,然后是 2 来自 C。给定每个堆中的石头数,返回可以移除的最大石头数。例如,在 的情况下
3,4,5
,可以移除的最大石头数是9
- 首先是B 的 2 个和 C 的 4 个,然后是 A 的 1 个和 B 的 2 个。
我编写了代码,其中我从 B 中删除了 2 的倍数,从 A 中删除了单数,然后从 C 中删除了 2 的倍数,从 B 中删除了单数,如下所示:
#include<algorithm>
#include<cstdio>
#include<iostream>
using namespace std;
int main() {
int n;
cin >> n;
ios_base::sync_with_stdio(false);
cin.tie(null);
while(--n) {
int a, b, c, ans=0;
cin >> a >> b >> c;
while(a>=1 && b>=2) { //This one
a--;
b-=2;
ans+=3;
}
while(b>=1 && c>=2) { //That one
b--;
c-=2;
ans+=3;
}
cout<<ans<<"\n";
}
return 0;
}
这打破了3,4,5
上面给出的例子- 我的输出6
不是9
. 通过判断的其他解决方案交换了上面评论的两个循环。
虽然我理解上失败的例子,我无法直观地了解什么是交换两个环路实现之间的区别-这是为什么有必要对工作堆B
和C
第一,在工作前A
和B
?
注意:我已经从问题中删除了这个问题实际上不需要的其他细节。
如果考虑 中石头的价值B
,每取一块石头就相当于取两块石头C
,但取每块石头A
相当于取两块石头B
,不取一块石头C
。
所以,为了最大化石头的数量,你要先从 中取出石头B
,然后从 中取出A
。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句