Font Size

原题：Font Size

原题大意

史蒂文喜欢看书。他现在读的这本书由N个段落组成，第i个段落包含ai个字符。现在他决定增加字符的字体大小。但史蒂文手机屏幕的尺寸有限。其宽度为W，高度为H。因此，如果字符的字体大小为S，则只能在一行中显示⌊W/S⌋个字符，并在页面中显示⌊H/S⌋行。（⌊x⌋是不大于x的最大整数）
所以这里的问题是，如果史蒂文想控制页数不超过P，他可以设置的最大字体大小是多少？请注意，段落必须以新行开头，段落之间没有空行。

算法分析

二分，但是二分有几种写法：

规定范围里的最大值（如果连续两个数，偏向右边的数）

m = l+(r-l+1)/2;
if(check(m)) l = m;
else r = m-1;

规定范围里的最小值（如果连续两个数，偏向左边的数）

m = l+(r-l)/2;
if(check(m)) l = m+1;
else r = m;

小于一个精度

while(r-l < 1e-5){
    m = (l+r)/2;
    if(check(m)) l = m;
    else r= m;
}

程序代码

#include <bits/stdc++.h>
using namespace std;
int T, p, w, h, n;
int a[1050];
bool check(int m){
            int cnt = 0;
            int t1 = w/m, t2 = h/m;
            for(int i = 0; i < n; i++)
            {
                int t = a[i] / t1;
                int tt = a[i] % t1;
                if(tt != 0) t++;
                cnt+=t;
            }
            int temp = cnt / t2;
            int tt = cnt % t2;
            if(tt !=0) temp++;
            if(temp <= p) return true;
            return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while(T--){
        cin >> n >> p >> w >> h;
        for(int i = 0; i < n; i++)
            cin >> a[i];
        int l, r, m;
        l = 1, r = min(w,h);
        while(l<r){
            m = l+(r-l+1)/2;
            if(check(m)) l = m;
            else r = m-1;
        }
        printf("%d\n", l);
    }
    return 0;
}