勵志用少的代碼做高效表達

---

Problem describe

Benjamin is going to host a party for his big promotion coming up.
Every party needs candies, chocolates and beer, and of course Benjamin has prepared some of those. But as everyone likes to party, many more people showed up than he expected. The good news is that candies are enough. And for the beer, he only needs to buy some extra cups. The only problem is the chocolate.
As Benjamin is only a ‘small court officer’ with poor salary even after his promotion, he can not afford to buy extra chocolate. So he decides to break the chocolate cubes into smaller pieces so that everyone can have some.
He have two methods to break the chocolate. He can pick one piece of chocolate and break it into two pieces with bare hand, or put some pieces of chocolate together on the table and cut them with a knife at one time. You can assume that the knife is long enough to cut as many pieces of chocolate as he want.
The party is coming really soon and breaking the chocolate is not an easy job. He wants to know what is the minimum number of steps to break the chocolate into unit-size pieces (cubes of size 1 × 1 × 1). He is not sure whether he can find a knife or not, so he wants to know the answer for both situations.

Input

The first line contains an integer T(1<= T <=10000), indicating the number of test cases.
Each test case contains one line with three integers N,M,K(1 <=N,M,K <=2000), meaning the chocolate is a cube of size N ×M × K.

Output

For each test case in the input, print one line: “Case #X: A B”, where X is the test case number (starting with 1) , A and B are the minimum numbers of steps to break the chocolate into N × M × K unit-size pieces with bare hands and knife respectively.

Sample Input

2
1 1 3
2 2 2

Sample Output

Case #1: 2 2
Case #2: 7 3

---

分析

題意：給定一個N*M*K的巧克力塊，問用手掰或用刀切各需多少步才能把巧克力塊變成N*M*K個1*1*1的單元塊。 用手掰一次只能掰一塊，用刀切可以切一行或者一列。

用手掰：很好算： N*M*K-1即可。

用刀切：注意：切的過程中方塊是可以改變位置 ，舉例：切割長寬高為1*4*1的方塊：

這樣，一共兩刀即可將所有方塊分割。

分析到這里，不難看出規律：

首先將長方體分為長寬高三個參數，分別考慮

則每個參數分別切割的次數一定與2的冪次有關，即： 2^n<=長或寬或高, n取最大值。 如：4就切兩刀，8就切三刀，若在4-8之間，則切3刀。（畫一畫就明白了）

貼上最后的代碼

#include<bits/stdc++.h> using namespace std; int main() {int T; cin>>T; for(int i = 1; i <= T; i++) {long long l, w, h; cin>>l>>w>>h;long long sum2=0;sum2 += ceil(1.0*log(l)/log(2));sum2 += ceil(1.0*log(w)/log(2));sum2 += ceil(1.0*log(h)/log(2));printf("Case #%d: %lld %lld\n", i, (l*w*h-1), sum2);} return 0; } 超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的14行代码AC_Break the Chocolate HDU-4112（数学推导+解析）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。