zoj 3590 – -3+1

给一堆正整数,每个有效操作为从某一个数字里面减去 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】

发表评论

电子邮件地址不会被公开。 必填项已用*标注