CodeForces 626C Block Towers

Posted on By 二价氢

题目大意

给定,要求个互不相同的数,其中有个2的倍数,个3的倍数,求这些数里最大值的最小值。其中

(这里的说明有些不准确,具体的参考原文)

做法

我们知道,在每6个数里,有3个2的倍数,与2个3的倍数,其中一个是2的倍数,于是我们可以进行分配,使得2的倍数与3的倍数的数量尽量平均。所以答案就是满足的最小。复杂度

上面是题目作者给出的一种做法,我想出了另一种做法,即尽量满足2的倍数与3的倍数的个数尽量平均的分配的贪心算法,具体可以参考下面的代码,复杂度

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000 * 5 + 5;
bool used[maxn];
int main() {
    int n, m, n1 = 0, m1 = 0;
    cin >> n >> m;
    used[0] = true;
    while (n || m) {
        if (n > m) {
            while (used[n1])
                n1 += 2;
            used[n1] = true;
            n--;
        } else {
            while (used[m1])
                m1 += 3;
            used[m1] = true;
            m--;
        }
    }
    cout << max(n1, m1) << endl;
    return 0;
}