d042.
Q_3_14 線性函數 (@@)
Content
有 $N$ 個線性函數 $f_i(x)=a_ix+b_i$，$1 \leq i \leq N$ 。定義 $F(x) = \displaystyle\max_i f_i(x)$。
輸入$c_i$， $1 \leq i \leq m$，請計算 $\displaystyle\sum^{m}_{i=1}F(c_i)$。
Input
第一行是 $N$ 與 $m$。接下來有 $N$ 行，依序每行兩個整數 $a_i$ 與 $b_i$ ，最後一行有 $m$ 個整數 $c_1, c_2, …, c_m$。
每一行的相鄰數字間以空白隔開。$N≤10^5$，$m≤5 \times 10^4$，輸入整數絕對值不超過 $10^7$，答案不超過 $10^{15}$。
Output
計算結果。
Sample Input
#1
4 5 -1 0 1 0 -2 -3 2 -3 4 -5 -1 0 2
Sample Output
#1
15
測資資訊：
記憶體限制：
256
MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
Hint ：
給 N 個線性函數(一次函數)，另外定義 F 是這些函數的最大值，現在給 m 個 x 值，要計算 F 在這些點的函數值總和，也就是對每一個 x 值，要計算這些線性函數的最大值。直接的做法全部計算取最大，總共需要O(mn)，效率不佳。請看下圖。藍線是這些線性函數，紅線就是F，他必定會形成一個(向下)凸的形狀，而且是一段一段的，每一段都是原來的某個藍線(函數)，如果我們可以找出這個紅線，計算這些函數值就沒問題了。我們需要一個觀察：若 f 與 g 是兩個線性函數，f 的斜率小於 g，那麼，在兩線的交點以前是 f 大，以後是 g 大。我們可以將這些直線根據斜率排序，然後逐一將直線加入 F 。這一題另外也有分治的演算法可以做，在後續章節中會再出現。
Tags:
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||