【20190802】【校招筆試題】瞌睡_網易

問題

小易覺得高數課太無聊了，決定睡覺。不過他對課上的一些内容挺感興趣，是以希望你在老師講到有趣的部分的時候叫醒他一下。你知道了小易對一堂課每分鐘知識點的感興趣程度，并以分數量化，以及他在這堂課上每分鐘是否會睡着，你可以叫醒他一次，這會使得他在接下來的k分鐘内保持清醒。你需要選擇一種方案最大化小易這堂課聽到的知識點分值。

輸入描述：

第一行 n, k (1 <= n, k <= 105) ，表示這堂課持續多少分鐘，以及叫醒小易一次使他能夠保持清醒的時間。

第二行 n 個數，a1, a2, ... , an(1 <= ai <= 104) 表示小易對每分鐘知識點的感興趣評分。

第三行 n 個數，t1, t2, ... , tn 表示每分鐘小易是否清醒, 1表示清醒。

輸出描述：

小易這堂課聽到的知識點的最大興趣值。

輸入例子1：

輸出例子1：

16

思路及解答

# 分析了題目，用了數學思維解決問題。
# 周遊每一個 t (叫醒的時刻)，求得當時的知識點分值，最後取最大。
# 分值 = sum(scores * awake) + sum(scores[t:t+k-1]) - sum(scores[t:t+k-1] * awake[t:t+k-1])，把 scores 清單和 awake 清單對應寫在一起，就能想明白了。
# 算法複雜度太高，已逾時。AC僅僅0.5。
import sys
n, k = map(int, sys.stdin.readline().strip().split())  
scores = sys.stdin.readline().strip().split()   
scores = [int(tmp1) for tmp1 in scores]
awake = sys.stdin.readline().strip().split()
awake = [int(tmp2) for tmp2 in awake]
result = []
for t in range(n):
    res1, res2, res3 = 0, 0, 0
    for i in range(n):
        res1 += scores[i] * awake[i]
    if t + k <= n:
        for j in range(t, t+k):
            res2 += scores[j] * awake[j]
        for m in range(t, t+k):
            res3 += scores[m]
    else:
        for j in range(t, n):
            res2 += scores[j] * awake[j]
        for m in range(t, n):
            res3 += scores[m]
    result.append(res1 + res3 - res2)
print(max(result))

# 略微有所優化，但依舊不起本質性作用。
import sys
n, k = map(int, sys.stdin.readline().strip().split())
scores = sys.stdin.readline().strip().split()
scores = [int(tmp1) for tmp1 in scores]
awake = sys.stdin.readline().strip().split()
awake = [int(tmp2) for tmp2 in awake]
result = 0
start = 0
for index in range(n):   # 不是從頭開始周遊，而是從第一個 awake 為0 的時候開始周遊。
    if awake[index]:
        start += 1
    else:
        break
for t in range(n):
    res1, res2, res3 = 0, 0, 0
    for i in range(n):
        res1 += scores[i] * awake[i]
    if t + k <= n:
        for j in range(t, t+k):
            res2 += scores[j] * awake[j]
        for m in range(t, t+k):
            res3 += scores[m]
    else:
        for j in range(t, n):
            res2 += scores[j] * awake[j]
        for m in range(t, n):
            res3 += scores[m]
    tmp = res1 + res3 - res2
    result = tmp if tmp > result else result   # 更新最大值，不存儲每個 t 對應的 tmp。
print(result)

# 略微有所優化，依舊不起本質作用。（僅提升到了 0.6）
import sys
n, k = map(int, sys.stdin.readline().strip().split())
scores = sys.stdin.readline().strip().split()
scores = [int(tmp1) for tmp1 in scores]
awake = sys.stdin.readline().strip().split()
awake = [int(tmp2) for tmp2 in awake]
result = 0
start = 0
for index in range(n):    # 從第一個不清醒時刻開始周遊即可。
    if awake[index]:
        start += 1
    else:
        break
for t in range(start, n-k+1):   # 到 t-k 時刻即可，因為後面再周遊，一定不如 n-k 時叫醒知識點值大。
    res1, res2, res3 = 0, 0, 0
    for i in range(n):
        res1 += scores[i] * awake[i]
    for j in range(t, t+k):
        res2 += scores[j] * awake[j]
    for m in range(t, t+k):
        res3 += scores[m]
    tmp = res1 + res3 - res2
    result = tmp if tmp > result else result   # 更新最大值，不存儲每個 t 對應的 tmp。
print(result)           

 下面參考牛客網友：瞌睡_牛客網

n, k = list(map(int, input().split()))
scores = list(map(int, input().split()))
awake = list(map(int, input().split()))

# 先計算最初所有清醒時刻分值之和，這裡做了一個很巧妙的事情：把清醒時刻的分值加了之後，把其分值置零（為了防止後續再次重複加，大吼一聲 666！）
initi_score = 0
for i in range(n):
    if awake[i]:
        initi_score += scores[i]
        scores[i] = 0    # 操作666

# 計算因為叫醒他，分值增加的那一部分
max_boost_score = 0
for t in range(n):   # 提前結束循環的條件，注意：不一定是從非清醒狀态開始加，見下面測試用例。
    if not awake[t]:   # 從非清醒狀态叫醒才能最佳
        boost_score = sum(scores[t: min(t+k, n)])
        max_boost_score = max(boost_score, max_boost_score)
        if t > n - k + 1:
            break
result = initi_score + max_boost_score
print(result)           

知識點

1. 輸入輸出的問題——用 input 來寫（前面一篇用的 sys.stdin.readline()）

（參考：瞌睡_網易筆試題_牛客網）

# 單行輸入，此時有兩個元素，用list()把它變成了清單
nk = list(map(int, input().split()))

# 把清單兩個元素取出來
n = nk[0]
k = nk[1]

# 再擷取第二行輸入
a = list(map(int, input().split()))

# 擷取下一行輸入（即第三行）
t = list(map(int, input().split()))           

2. input 的用法

(1) Python2 是 raw_input()；Python3 是 input() 。

（參考：Python3 input() 函數）

（參考：Python input() 函數）

（參考：Python2.x 和 Python3.x 中 raw_input( ) 和 input( ) 差別）

(2) Python3 中 input 讀出來的一切資訊都是 string 類型，若想轉換成 int 型，可以用 eval() 或者 int()。

(3) 多個參數輸入

① 輸入個數确定時

>>> a, b, c = input('...>').split()
...>11 22 33

# 那麼有：
    a = '11'
    b = '22'
    c = '33'
           

② 輸入個數不确定時，把它們放在一個清單裡面

>>> list = []
>>> list = input('...>').split()
...>11 22 33 44

# 那麼有：
    ['11', '22', '33', '44']
           

（參考：python input 詳解）