HDU - 4112 Break the Chocolate（规律）

题意：有一块n*m*k的巧克力，最终需要切成n*m*k个1*1*1的块，问用以下两种方法最少掰多少次能达到目的：

1、用手掰：每次只能拿出一块来掰；
2、用刀切：可以把很多已经分开的块摞在一起一刀切下来

分析：

1、用手掰，需要n*m*k-1次。

2、用刀切，可以分别考虑长宽高，计算长宽高分别切成单位长度所需要的最少次数，相加即可。

二分切，可得最少次数。规律为，长度为x最少需切ceil(log2(x))次。

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

int main(){

    int T;

    scanf("%d", &T);

    int kase = 0;

    while(T--){

        LL n, m, k;

        scanf("%lld%lld%lld", &n, &m, &k);

        LL cnt1 = n * m * k - 1;

        LL cnt2 = (LL)ceil(log2((double)n)) + (LL)ceil(log2((double)m)) + (LL)ceil(log2((double)k));

        printf("Case #%d: %lld %lld\n", ++kase, cnt1, cnt2);

    }

    return 0;

}

巴特西

HDU - 4112 Break the Chocolate（规律）

最新文章

热门文章