poj2566

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog

poj2566

链接

题意

        给定一个数组和一个值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)