题目大意
给定\(n\)和\(m\)，要求\(n + m\)个互不相同的数，其中有\(n\)个2的倍数，\(m\)个3的倍数，求这些数里最大值的最小值。其中\(0\le n, m \le 10^6\)
（这里的说明有些不准确，具体的参考原文）
做法
我们知道，在每6个数里，有3个2的倍数，与2个3的倍数，其中一个是2的倍数，于是我们可以进行分配，使得2的倍数与3的倍数的数量尽量平均。所以答案就是满足\(n\le \frac{X}{2}, m\le \frac{X}{3}, m + n\le \frac{X}{2} + \frac{X}{3} - \frac{X}{6}\)的最小\(X\)。复杂度\(O(1)\)
上面是题目作者给出的一种做法，我想出了另一种做法，即尽量满足2的倍数与3的倍数的个数尽量平均的分配的贪心算法，具体可以参考下面的代码，复杂度\(O(n + m)\)
代码
#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;
}