tnfshoj 196 / A. 難忘的回憶
- problem link
-
題目理解:給 N (N <= 10^5) 個數字,第 i 個為 Si (0 <= Si <= 10^5),給 Q (Q <= 10^5) 個詢問,第 i 個為 Wi (0 <= Wi <= 2 * 10^5),問是否存在 Si + Sj == Wi (i <= j)?
-
解法:
首先先將 S 照升序排序
對於每筆詢問,先特判一定無解的狀況(S[0] * 2 > W or S[N-1] * 2 < W) 跟 i == j 的狀況(此時 W 為偶數,二分搜 W/2 即可)接著尋找 i < j 的狀況
維護兩個下標 i, j
首先初始化 i, j
j 為最大的 j 使得 S[j] <= W (S[j] > W 顯然無解)
i 為最小的 i 使得 S[i] >= W - S[j] (S[i] < W - S[j] 顯然無解)接著對於每個 i ,迭代尋找最大的 j 使得 S[i] + S[j] <= W
對於下一個 i 而言,因為 S[i] + S[j + 1] > W 而且 S[i + 1] >= S[i]
所以 S[i + 1] + S[j + 1] > W,故 i + 1 對應的 j 可以從當前的 j 開始尋找 - 複雜度 O(QN)
每筆詢問最多遍歷 N 個數字,有 Q 筆詢問 其實照這題的規模這樣的複雜度應該是過不了的,可能是測資太善良吧
測資更新惹,我的 code TLE 惹
等我或其他人想出更好的解再更新吧- 蜥蜴說是用 FFT 解,然而我不會 QAQ