• 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