^

Young Anything I do that may help others, I'll post it here.

hihocoder 1288 — font size

18 Oct 2016

1 描述

Steven loves reading book on his phone. The book he reads now consists of N paragraphs and the i-th paragraph contains ai characters.

Steven wants to make the characters easier to read, so he decides to increase the font size of characters. But the size of Steven’s phone screen is limited. Its width is W and height is H. As a result, if the font size of characters is S then it can only show ⌊W / S⌋ characters in a line and ⌊H / S⌋ lines in a page. (⌊x⌋ is the largest integer no more than x)

So here’s the question, if Steven wants to control the number of pages no more than P, what’s the maximum font size he can set? Note that paragraphs must start in a new line and there is no empty line between paragraphs.

2 输入

Input may contain multiple test cases.

The first line is an integer TASKS, representing the number of test cases.

For each test case, the first line contains four integers N, P, W and H, as described above.

The second line contains N integers a1, a2, … aN, indicating the number of characters in each paragraph.

For all test cases,

1 <= N <= 10^3,

1 <= W, H, ai <= 10^3,

1 <= P <= 10^6,

There is always a way to control the number of pages no more than P.

3 输出

For each testcase, output a line with an integer Ans, indicating the maximum font size Steven can set.

样例输入

2
1 10 4 3
10
2 10 4 3
10 10

样例输出

3
2

4 实现

4.1 暴力

from math import *


while True:
    try:
        T = int(raw_input().strip())
        for i in xrange(T):
            max_S = 0

            [N, P, W, H] = [int(x) for x in raw_input().strip().split()]
            a = [int(arg) for arg in raw_input().strip().split()]

            for S in xrange(min(W, H), 0, -1):
                cols = floor(W / S)
                row = floor(H / S)
                lines = [ceil(ai / cols) for ai in a]
                rows = sum(lines)
                pages = int(ceil(rows / row))
                if pages <= P and S > max_S:
                    max_S = S
            print max_S
            
    except EOFError:
        break

4.2 二分

from math import *

while True:
    try:
        T = int(raw_input().strip())
        for i in xrange(T):

            [N, P, W, H] = [int(x) for x in raw_input().strip().split()]
            A = [int(arg) for arg in raw_input().strip().split()]


            def F(s, w=W, h=H, a=A):
                cols = floor(w / s)  # 屏幕的宽最多能容纳的字符个数(即屏幕的最多列数)
                row = floor(h / s)  # 屏幕的高最多能容纳的字符个数(即屏幕的最多行数)
                lines = []
                for ai in a:
                    lines.append(ceil(ai / cols))  # 各段需要的行数
                rows = sum(lines)  # 需要的总行数
                pages = ceil(rows / row)  # 需要的页数
                return int(pages)


            l_S = 1
            r_S = min(W, H)
            l_P = F(l_S)
            r_P = F(r_S)

            if l_P > P:
                print 0
            else:
                while r_P > P and (l_S + 1) < r_S:
                    mid_S = int(floor((l_S + r_S) / 2))
                    mid_P = F(mid_S)

                    if mid_P < P:
                        l_S = mid_S
                        l_P = mid_P
                    else:
                        r_S = mid_S
                        r_P = mid_P
                if r_P <= P:
                    print r_S
                else:
                    print l_S

    except EOFError:
        break

总结

  1. 为了快速AC，应该先尝试下暴力算法，这一题给的P的范围不超过10^6,并不大，所以能暴力则暴力，考试不是项目，没必要给出最优解！
  2. 在二分的时候，没必要设计得特别精巧，把所有情况考虑完全了，可以多写点逻辑流程。思考最精巧的逻辑循环判断是完全浪费时间，考试就是为了能快速实现！

Related Posts