微软2016校园招聘4月在线笔试 A FontSize

题目链接：http://hihocoder.com/problemset/problem/1288

分析：题目中所求的是最大的FontSize(记为S)，其应该满足P*[W/S]*[H/S] >= Sum,其中Sum是字符的总数。但是我们也要注意，段与段之间不能在同一行，所以根据上面公式求出来的S不一定满足条件，还要对其进行检验。下面是我的代码。

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int num[1001];
 7 int N , P, W,H;
 8 
 9 bool check(int font,int N ,int p){
10 
11     int page = 0 , line = 0;
12 
13     int lc = W/font;
14     int wc = H/font;
15 
16     for(int i = 0 ; i < N ; i ++){
17         line += num[i]/lc;
18         if(num[i]%lc) line ++;
19     }
20 
21     page = line/wc;
22     if(line%wc) page ++;
23 
24     return (page<=p);
25 }
26 
27 int main()
28 {
29     int cas,lines;
30     scanf("%d",&cas);
31     while(cas --)
32     {
33             scanf("%d%d%d%d",&N,&P,&W,&H);
34             int sum = 0;
35 
36             for(int i = 0 ; i < N ; i ++){
37 
38                 scanf("%d",&num[i]);
39                 sum += num[i];
40             }
41 
42             double cc = (double)1/sum * P*W*H;
43             int font = sqrt(cc) + 1;
44 
45             int lc = H/font ;
46             int wc = W/font ;
47 
48             while(P*lc*wc < sum || !check(font,N,P)){
49                     font --;
50                  lc = H/font ;
51                  wc = W/font ;
52             }
53             printf("%d
",font );
54     }
55 
56     return 0;
57 }