链接
题意
给定一个数组和一个值t，求一个子区间使得其和的绝对值与t的差值最小，如果存在多个，任意解都可行。
n<1e5
题解
子区间和的绝对值
那就可以对前缀和排序了，因为abs(presum[i]-presum[j])=abs(presum[j]-presum[i]) 根ij大小无关
于是可以对前缀和排序，
化简题目为：
求两个前缀和a,b，使得abs(a-b)于t相差最近
我们对前缀和排序
dp[i]取abs(abs(presum[i]-presum[dp[i]])-t)最小的那个
显然dp[i]具有关于i具有单调性。
于是可以优化为O(n)