#34717: 解題的想法


asnewchien@gmail.com (david)

School : No School
ID : 68108
IP address : [114.42.148.26]
Last Login :
2024-06-20 14:02:44
k290. 借款金額 (Loan) -- TOI練習賽202303潛力組第1題 | From: [1.168.18.231] | Post Date : 2023-04-10 15:16

這一題的 n 可以到 2*10^5
所以 2 分搜時帶入 x 去跑迴圈,應該會超時。

以第一個範例

6 5
18 6 0 19 19 4

R = 5 可以假設一個係數 1/R = 0.2

如果本金是 x

((1.2x - a1) * 1.2 - a2) * 1.2 - a3 ...

到最後一期的餘額要 <= 0

式子可以簡化為

x * 1.2^n - a1 * 1.2^(n-1) - a2 * 1.2^(n-2) ...

從 a1 開始可先加總

二分搜時只要帶入 x 很快就能驗證 x 可否還清。

但是有小數取整的問題,還要再想想 ...

 
ZeroJudge Forum