poj2566

2019-08-05

字数统计: 277字 | 阅读时长≈ 1分

next hexonext butterfly volantis yearn yilia shoka indigo apollo landscape cactus matery icarus fluid material

转移自老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)

本文作者： fightinggg
本文链接： http://fightinggg.github.io/yilia/yilia/poj2566.html
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！

jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true