#41220: O(1)解,但不一定最好(還需要會一點微分)


yihao3138@gmail.com (Yi Hao Su)

學校 : 不指定學校
編號 : 274855
來源 : [36.239.4.112]
最後登入時間 :
2024-09-14 18:56:35
f312. 1. 人力分配 -- 2020年10月APCS | From: [36.239.56.204] | 發表日期 : 2024-07-11 23:28

根據題設,我們有 x_2 = n - x_1,並設 y = y_1 + y_2,其中 y 在區間 [0, n] 的局部最大值為 m。為了求 y 的極值,我們令 dy/dx_1 = 0,解得:

x_1 = (2*a_2*n - b_1 + b_2) / (2a_1 + 2a_2)

接著,考慮 a_1 + a_2 > 0 的情況:

  • 若 x_1 > n/2,則 m 出現在 x = 0 處。
  • 若 x_1 < n/2,則 m 出現在 x = n 處。
  • 若 x_1 = n/2,則 m 出現在 x = 0 和 x = n 處皆可。

再考慮 a_1 + a_2 < 0 的情況:

  • 若 x_1 > n,則 m 位於 x = n 處。
  • 若 x_1 < 0,則 m 位於 x = 0 處。
  • 若 0 <= x_1 <= n,則 m 位於 x = round(x_1) 處。

保險起見,再一下考慮 a_1 + a_2 = 0 的情況:

  • 觀察一次項之正負判斷 m 位於何處即可,線性最棒了

 

最後,輸出 m 的值。

 
ZeroJudge Forum