2019字节跳动春招题目

2019字节跳动算法岗春招（不是2020届的秋招！），共四道编程题，没有选择题。笔试的时候只做出来了前两道，这里参考了大佬 Azhao1993 的解题思路， 把后两道的解法整理一下。

Q3 编程比赛

现在有n人参加编程比赛，比赛结束后每个人都得到一个分数。现在所有人铺成一圈（第1个和第n个相邻）领取奖品，要求：

1.如果某个人的分数比左右的人高，那么奖品数量也要比左右的人多；

2.每个人至少得到一个奖品。

输入描述：

第一行是整数n，表示测试样例数

每个测试样例的第一行是一个正整数，表示参加比赛的人数(0<n<100,000)

第二行是n个正整数，a[i] (0 <a[i]<10,000), 表示的从第1个人到第n个的分数

输出描述：对每个测试样例，输出应该准备的最少奖品

示例1

输入

2

2

1 2

4

1 2 3 3

输出

3

8

思路： 将选手从左到右排列在一个列表中，首尾相连，然后从左到右和从右到左分别使用贪心算法。

解答 (Python3)：

# 读入输出
import sys
try: 
    while True:
        line = sys.stdin.readline().strip()
        if line == '':
            break 
        lines.append(line)
except: 
    pass

def main():
    N = int(lines[0]) # 测试样例数
    for i in range(N):
        m = int(lines[i*N+1]) #选手数目
        s = [int(item) for item in lines[i*N+2].split(' ')]# 选手的分数
        assert m == len(s), print("Error!")
        r = [1 for _ in range(m)] # 选手的奖品数，初始值为每个选手1个奖品
        # 首尾相连
        m += 1
        s.append(s[0])
        r.append(1)
        
        while True:
            flag = False #判断当前循环内有没有发生奖品数的变化，若没有则说明当前奖品数已满足要求，可以退出当前循环。
            #从左到右，若右边选手的分数高于左边，但奖品数低于或等于左边，则右边选手的奖品数=左边选手的奖品数+1
            for j in range(m-1):
                if s[j] < s[j+1] and r[j] >= r[j+1]:
                    r[j+1] = r[j] +1
                    flag = True
            r[0] = r[-1]
            #从右到左，若左边选手的分数高于右边，但奖品数低于或等于右边，则左边选手的奖品数=右边选手的奖品数+1
            for j in range(m-1, 1, -1):
                if s[j] < s[j-1] and r[j] >= r[j-1]:
                    r[j-1] = r[j] +1
                    flag = True
            r[-1] = r[0]
            if not flag:
                break
        result = sum(r[0:len(s)-1])
        #输出结果
        print(result)
if __name__ == '__main__':
    main()
           

Q4 割绳子

有N根绳子，第i根子长度为Li，现在需要M根等长的绳子，你可以对n根绳子进行任意裁剪（不能拼接），请你帮忙计算出这m根绳子最长的长度是多少。

输入描述：

第一行包含2个正整数N，M， 表示N根原始的绳子和最终需要M根绳子数

第二行包含N个整数，第i个整数Li表示第i根绳子的长度

其中

1<=N, M<=10000

0<Li<1000000000

输出描述：

对每一个测试用例，输出一个数字，表示裁剪最后的长度，保留两位小数

思路：二分法

解答 (Python3)：

# 读入输出
import sys
try: 
    while True:
        line = sys.stdin.readline().strip()
        if line == '':
            break 
        lines.append(line)
except: 
    pass

N = lines[0].split(' ')[0]
M = lines[0].split(' ')[1]
L = [int(item) for item in lines[1].split(' ')]

def main():
    LENGTH = sum(L)#总绳长
    l = 0
    r = LENGTH
    result = 0
    while (r-l) > 1e-4:#二分法，当l-r满足精度时跳出循环
        mid = (l+r)/2.0
        if mid == 0:
            break
        if sum([int(item/mid) for item in L]) >= M:#如果可以截成M段长度为mid的绳子
            l = mid
            result = mid
        else:
            r = mid
    print(round(mid, 2))
        
if __name__ == '__main__':
    main()