微软2016校园招聘4月在线笔试 A. Font Size 题解

最后编辑于: 2016-04-09

题解

这种题的名字叫做阅读理解，读懂题就可以写出来。注意到在试S时递减步长是1，明显存在冗余，设计一个方法自适应地增大步长能够降低时间复杂度。

#include<iostream>
#include<cmath>
#include<string>
#include<vector>

int TASKS, N, P, W, H;

bool is_ok(std::vector<int>& paras, int s)
{
    int max_per_line = W / s;
    int max_lines = H / s;
    int lines = 0;
    for (size_t i = 0; i < N; ++i)
        lines += (int)ceil((double)paras[i]/max_per_line);
    return lines <= P * max_lines ? true:false;
}

int main(void)
{
    std::cin >> TASKS;
    std::vector<int> paras;
    while(TASKS--)
    {
        paras.clear();
        std::cin >> N >> P >> W >> H;
        int n_cnt = N;
        while(n_cnt--)
        {
            int tmp;
            std::cin >> tmp;
            paras.push_back(tmp);
        }
        int wid = W;
        while(wid)
        {
            if(is_ok(paras, wid))
                break;
            wid--;
        }
        std::cout << wid <<std::endl;
    }
    return 0;
}