给一堆正整数,每个有效操作为从某一个数字里面减去 3,再在任意一个数字里面加上 1,求最多可以做多少个操作。
思路很简单,先把整 3 个的取出来,每个可以产生一个游离的 1,记在 a 中。 然后还没匹配完的有 mod 3 余 1 的 a1 个,余 2 的 a2 个; 只要 a > 0,就可以完全消去所有的 a1,a 的数量不改变; 然后,每有两个 a 值,可以消去一个 a2,a 的数量减一; 完了如果 a 还有剩,那么自己消去直到没有为止。
// 3493735 2013-12-21 22:38:46 Accepted 3590 C++ 20 272 呆滞的慢板
include
include
using namespace std;
int main() {
long long n, i, a, a1, a2, x, ans;
while(cin >> n) {
for(i = a = a1 = a2 = 0; i < n; ++i) {
cin >> x;
a += x / 3;
switch(x % 3) {
case 1: ++a1; break;
case 2: ++a2; break;
}
}
ans = a;
if(a > 0) ans += a2;
while(a > 1 && a1 > 0) {
x = min(a1, a/2);
ans += x;
a1 -= x;
a = a - x;
}
if(a > 0) ans += (a - 1) / 2;
cout << ans << endl;
}
}
【转载请附】愿以此功德,回向 >>
原文链接:http://www.huangwenchao.com.cn/2013/12/zoj3590.html【zoj 3590 – -3+1】