Break the Chocolate SPOJ

Break the Chocolate

题意:你有一块N*M*K的巧克力和一把无限长度的刀。要把整块巧克力变成1*1*1的。问用手掰巧克力(每次只能把一块掰成两块)和用刀切的最少操作数。

题解:

​ 用手掰肯定怎么掰都是(N*M*K-1)次。如果硬要推的话,可以模拟一下,先把第一维掰成(N-1)块,然后类推后两维,这样答案是((N-1) + N*(M-1 + M*(k-1)) = N*M*K-1)

​ 用刀切呢?每次可以把所有巧克力切成两块,所以是(log_2(N)+log_2(M)+log_2(K))向上取整。

#include <bits/stdc++.h>
#define fopi freopen("in.txt", "r", stdin)
#define fopo freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int> Pair;
const int maxn = 1e7 + 10;
const double eps = 1e-6;

LL cut(int n) {
    return (LL)ceil(log(n) / log(2) - eps);
}

int T;
int main() {
    scanf("%d", &T);
    for (int ca = 1; ca <= T; ca++) {
        LL n, m, k;
        scanf("%lld%lld%lld", &n, &m, &k);
        printf("Case #%d: %lld %lld
", ca, n*m*k - 1, cut(n) + cut(m) + cut(k));
    }
}
原文地址:https://www.cnblogs.com/ruthank/p/11352029.html