Equal Sum Subarrays (USACO Gold 2023 February)

这个题应该可以感觉到有比较直观的 $\mathcal{O}(N^3)$ 解法，而根据一般的复杂度经验， $N=400$ 是 $\mathcal{O}(N^3)$ 的规模上限，但我们看到此题特意标明了时间限制是3秒（多 $50\%$ ），所以这指向 $\mathcal{O}(N^3)$ 应该是能够通过的。

具体的办法，通过前缀和，暴力生成所有的subarrays的和，然后把这些和与subarray范围一起，按和的大小排序，然后对每个 $i$ 用双指针扫描这个排序好的列表，记录下上一个包含 $a[i]$ 的和的数值（代码中with变量），以及上一个不包含 $a[i]$ 的和的数值（without），abs(with-without)就是 $a[i]$ 需要改变的一个可能的值，在其中取最小值，就是对 $i$ 的结果。具体见代码。

官方解答中有进一步优化到 $\mathcal{O}(N^2\log N)$ 的解法，可以参考。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;
ll ps[505];
vector<pair<ll, pi>> sums;     // subarray sums
const ll INF = 1e18;
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        ll a;
        scanf("%lld", &a);
        ps[i] = ps[i-1]+a;
    }
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) // [i,j]
            sums.push_back({ps[j+1]-ps[i], {i,j}});
    sort(sums.begin(), sums.end());
 
    for (int i = 0; i < n; i++) {   // result for i
        ll ans = INF;
        ll with = INF, without = INF;
        for (auto e: sums) {
            if (e.second.first <= i && e.second.second >= i)
                with = e.first;
            else without = e.first;
            if (with != INF && without != INF)
                ans = min(ans, abs(with-without));
        }
        printf("%lld\n", ans);
    }
 
    return 0;
}