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()