Vijos 1361 天平称量 解题报告

利用分治求解，将n个球分成3份，取其中两份称量，若不等则较重的球必然在较大的一份中，否则较重的球必然在未称的的一份中。在此基础上再继续三分直到分得的一份中只包含一个球。

因此可以得到递推式f[i]=f[i div 3]+1(i mod 3=0),f[i div 3+1]+1(i mod 3<>0);

Vijos题解中许多人提到的利用公式trunc(ln(n)/ln(3))+1得到的结果对于n=3^i时是错误的，只是数据中没有这种情况。

R1070492 Accepted 100 From IwfWcf P1361    FPC Vivid Puppy 2008-11-18 17:35:46