HDU 5461 Largest Point：最大化 a*t_i² + b*t_j (i≠j)

題目大意

給定 n (≤ 5×10⁶) 個整數 t_i，及係數 a, b（絕對值 ≤ 10⁶）。從中選兩個不同下標 i, j，最大化 a*t_i² + b*t_j。多測試案例，總 n ≤ 5×10⁶。

核心觀察

t_i² 永遠非負，故 a*t_i² 的符號僅取決於 a；b*t_j 符號取決於 b 和 t_j 的符號。我們只需考慮極值候選：

• 將數組分為非負組 nz[] 和負組絕對值 ng[]，分別排序。
• 根據 a, b 的正負，枚舉極大/極小的幾個候選值組合即可（最多常數組）。

分類討論 (代碼邏輯)

// 非負組 nz 升序，負組絕對值 ng 升序
if (a >= 0 && b >= 0) {
    // 取最大的兩個非負數互換位置，或取最大負數絕對值配合最大非負
} else if (a >= 0 && b < 0) {
    // b<0 時希望 t_j 盡可能小（負數絕對值大），a>=0 取最大非負或負數絕對值
} else if (a < 0 && b >= 0) {
    // a<0 取 t_i 絕對值最小（即最接近 0），b>=0 取最大非負
} else { // a<0, b<0
    // 取 t_i 絕對值最小，t_j 絕對值最大（負數）
}

複雜度

排序 O(n log n)，但總 n ≤ 5e6 可接受；實際可用計數排序或桶排序優化到 O(n + V)（V=10⁶）。空間 O(n)。