9.23 华为笔试

9.24 update: 更新简单题解

#1 某种数学运算

import math
def s(c):
    n = math.floor(math.sqrt(c + 0.75) - 0.5)
    s = c - n ** 2 - n
    r = 2 * n
    if s > n:
        r += 1
    return r
print(s(int(input())))

本地计算结果，发现呈现 [0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8 ...] 的关系，推公式按照 c 反推 n 即可。

#2 某种 DP

n = int(input())
m = []
for i in range(2):
    m.append(list(map(int, input().split())))
c = [0]
d = [0]
for i in range(n):
    c.append(c[-1] + m[1][i])
    d.append(d[-1] + m[0][n - 1 - i])
result = float('inf')
for i in range(n):
    t = max(c[i], d[n - 1 - i])
    result = min(t, result)
print(result)

     A |x|  C 
  ------------
     D |y| B

小华走 A + x + y + B，小为走 max(C, D), 小华会选择最小的 max(C, D)。

#3 某种模拟

import bisect

[n, x, y] = map(int, input().split())
a = list(sorted(map(int, input().split())))
for i in range(n):
    a[i] = max(0, a[i] - i)
count = 0
index = 0
while x < y:
    index = bisect.bisect(a, x)
    if index == n:
        count += y - x
        break
    base = 2 * index - n
    target = min(a[index], y)
    diff = target - x
    if target == y and diff <= index:
        count += diff
        break
    if base < 0:
        count = -1
        break
    t = diff // base
    count += t * n
    x += base * t
print(count)

每次都要把所有的都打了之后才可以开始下一轮，因此先打等级低的。每轮的收益和当前能打过的人数有关系。之后模拟即可。