题意:给出n、m,请计算一个只有n个2的倍数和m个3的倍数构成并且没有重复的序列中最小的max(n*2, m*3)。


为了接下来学习01规划找到的这个题。

这个题有两种解法,一种是贪心,一种是二分。


我们先来看看贪心解法:


一、贪心:

首先,我们考虑到2的倍数和3的倍数是有他们的最小公倍数6的倍数的重复的。所以我们只需要先假定n就是n*2,m就是m*3,这时候可能有6的重复,所以我们从6开始不断增长6的倍数,然后对n、m进行判断,如果n小于或等于(等于是因为2的倍数等于3的倍数时,明显加2会使得值序列最大值更小)就n+=2,否则m+=3。这样直到6的倍数增长到大于n、m任意一方的时候就可以了。


代码如下:

StatusAccepted
Time15ms
Memory2056kB
Length297
LangGNU G++ 5.1.0


代码:

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
    int n, m;
    while(~scanf("%d%d", &n, &m)){
        n*=2, m*=3;
        for(int i=6;i<=min(n, m);i+=6){
            if(n<=m)n+=2;
            else m+=3;
        }
        printf("%d\n", max(n, m));
    }
    return 0;
}


二、二分


PS:真的要感慨自己学的少,今天才知道还能对答案进行二分的操作。


二分的思想就是:假设答案为mid。那么:

mid中2的倍数就是:mid/2

mid中3的倍数就是:mid/3

mid中6的倍数就是:mid/6


那假设真正的答案是ans。对于大于或者等于ans的mid来说,肯定有:mid/2+mid/3-mid/6>=n+m

同理,小于ans的肯定有mid/2+mid/3-mid/6<n+m

所以,我们假设l=1, r=无穷大,只要通过这两个条件不断对区间进行二分,必然会得到正确的答案。


代码:

StatusAccepted
Time15ms
Memory2056kB
Length496
LangGNU G++ 5.1.0


#include <iostream>
#include <cstdio>
using namespace std;
const int L=1, R=1e7;
int n, m;
bool check(int x){
    int num2=x/2;
    int num3=x/3;
    int num6=x/6;
    if(num2>=n&&num3>=m&&num2+num3-num6>=n+m)return 1;
    return 0;
}
int main()
{
    while(~scanf("%d%d", &n, &m)){
        int l=L, r=R, mid, ans;
        while(l<=r){
            mid=(l+r)>>1;
            if(check(mid))ans=mid, r=mid-1;
            else l=mid+1;
        }
        printf("%d\n", ans);
    }
    return 0;
}