Codeforces 429D Tricky Function：前綴和與最近點對

題目轉化

給定數組 a[1..n]，定義前綴和 s[i] = Σ a[k]。點 i 對應平面點 (i, s[i])。求任意兩點間歐氏距離平方的最小值。

關鍵觀察

距離平方 = (i-j)² + (s[i]-s[j])²。若固定橫向距離 d = i-j，則縱向差為 s[i]-s[i-d]。枚舉 d 從 1 到 n-1，內層枚舉 i 計算 (s[i]-s[i-d])²，取最小值加 d² 更新答案。

優化剪枝

若 d² 已 ≥ 當前最佳答案，後續 d 更大無需枚舉，直接 `break`。這使實際運行極快，接近 O(n√ans)。

代碼核心

ans = a[2]*a[2] + 1; // 初始上界
for (ll i=1; i ans) break;
    ll t = ans;
    for (int j=i+1; j<=n; ++j)
        t = min(t, (s[j]-s[j-i])*(s[j]-s[j-i]));
    ans = min(ans, t + i*i);
}

複雜度分析

最壞 O(n²)，但剪枝極強，隨機數據下接近 O(n log n)。n ≤ 10⁵ 可過。

總結

將數組問題幾何化為平面最近點對，利用前綴和性質與剪枝，以簡單雙循環解決看似困難的問題，體現「趁早想清楚，代碼很短」的競賽哲理。