HDU 5265 Pog Loves Szh II：排序+雙指針求模最大值

問題描述

給定 m 個整數和模數 p，從中選兩個數 a, b（可相同），使 (a + b) mod p 最大。m ≤ 100,000，多測試用例。

核心觀察

若 a + b < p，則 (a+b) mod p = a+b，最大值為最大的兩數之和。
若 a + b ≥ p，則 (a+b) mod p = a+b-p，我們希望 a+b 盡可能接近 2p-2（即 a+b-p 接近 p-2），但更直接的目標是使 a+b 在 [p, 2p-2] 區間內盡可能大，使餘數最大。

算法：排序 + 雙指針

1. 讀入數組並升序排序。
2. 若最大兩數之和 < p，直接輸出該和（無模運算影響）。
3. 否則，目標是找 a[i] + a[j] 使其模 p 最大。等價於：對每個 i，在 j < i 中找最大的 a[j] 使 a[i] + a[j] < p（則餘數為 a[i]+a[j]），或找最小的 a[j] 使 a[i] + a[j] ≥ p（則餘數為 a[i]+a[j]-p）。
4. 使用雙指針：i 從大到小遍歷，j 從小到大維護滿足條件的邊界，O(m) 求解。

關鍵代碼

sort(a, a+m);
if (a[m-1] + a[m-2] < p) {
    cout << a[m-1] + a[m-2] << '\n';
    continue;
}
int ans = 0;
int j = 0;
for (int i = m-1; i >= 1; i--) {
    while (j < i && a[i] + a[j] < p) j++;
    if (j < i) ans = max(ans, a[i] + a[j] - p);
    if (j > 0) ans = max(ans, a[i] + a[j-1]);
    if (ans == p-1) break; // 理論最大值，提前結束
}
cout << ans << '\n';

複雜度

• 排序：O(m log m)
• 雙指針掃描：O(m)
• 總體：O(m log m)，m=10⁵ 極快

總結

本題將模運算最大值轉化為有序數組中雙指針尋找最佳配對。關鍵在於：排序後，對每個大數 a[i]，最佳搭檔 a[j] 單調遞增，雙指針可線性掃描。注意提前剪枝（達到 p-1 即最優）。