題目：(官方網站似乎尚未公布…這裡憑比賽印象打出來)
現在有三條數列a、b、c，都恰有n項
(其中a,c可以1~10億，b可以0~100，n沒記錯應該有100000左右)
問要取最小的m(最少的訓練天數)能滿足
對於至少k對不同的i,j，存在a[i]+m*b[i]>c[j]
(也就是訓練m天馬的力量>對手馬的力量，勝k場)
程式碼：(待補)
訓練m天，就能讓所有的馬平均成長、不用煩惱幾天要訓練1號、另外幾天2號…
而且也不會有馬過度訓練太疲憊以致戰力減退這種情形(b都是非負整數)
所以可見
訓練的天數m取值越大，能獲勝的場數x就越多
於是想到二分搜尋答案，對天數m'可以經過O(nlgn)排序解出能贏幾場
再比較是否合乎贏k場的要求
總時間複雜度O(nlgnlgn)
沒有留言:
張貼留言