nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

poj2566

链接

http://poj.org/problem?id=2566

题意

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