Microsoft : Find the largest square fits a rectangle

Given a rectangle with known width and height, design an algorithms to fill
the rectangle using n squares(n is integer, also given) and make sure in the
result the wasting area is minimized. Length of square doesn't have to be integer.

I.e, given width=3,height=2,n=5, one solution is that rectangle can
be filled with five 1x1 squares and the wasting area is 1. Another
solution could be filled with five 0.9x0.9 squares, but the wasting area is more than first solution.

说说我的思路：

可以证明最优解的情况一定是方格可以填满行的，或是方格可以填满列的(填满了再往上排)。
可以分行列来考虑。
如果是行，行的长度为l.,考虑方格长度为l/n,l/(n-1)...l的情况，找最优值(二分优化)
在分列来考虑，记录最优值。

我的代码:

1. 
   
2. bool fits(float l, float w, int m, int n)
   
3. {
   
4.         assert(l>0 && w>=0 && m>0 && n>0);
   
5. 
   
6.         if (n <= m && w >= l/m)
   
7.                 return true;
   
8. 
   
9.         if (w < l/m) return false;
   
10. 
    
11.         return fits(l, w-l/m, m, n-m);
    
12. }
    
13. 
    
14. float CalcLen(int l, int w, int n)
    
15. {
    
16.         assert(l>0 && w>0 && n>0);
    
17. 
    
18.         int nLow = 1;
    
19.         int nHigh = n;
    
20.         int nBest = -1;
    
21. 
    
22.         while (nLow < nHigh)
    
23.         {
    
24.                 int nMid = (nLow + nHigh)/2;
    
25.                 if (fits(l, w, nMid, n))
    
26.                 {
    
27.                         nHigh = nMid-1;
    
28.                         nBest = nMid;
    
29.                 }
    
30.                 else
    
31.                         nLow = nMid+1;
    
32.         }
    
33. 
    
34.         if (nLow == nHigh && fits(l, w, nLow, n))
    
35.                 nBest = nLow;
    
36. 
    
37.         return (float)l/(float)nBest;
    
38. }
    
39. 
    
40. float GetLargest(int l, int w, int n)
    
41. {
    
42.         assert(l>0 && w>0 && n>0);
    
43. 
    
44.         float r1 = CalcLen(l, w, n);
    
45.         float r2 = CalcLen(w, l, n);
    
46. 
    
47.         return r1>r2?r1:r2;
    
48. }
    

复制代码