逐 梦
github
github
ACM模版
数论
数据结构
字符串
dp
图论
计算几何
思维与算法
黑科技
快读
ACM题型
数论
数据结构
字符串
dp
图论
计算几何
思维与算法
黑科技
生成博客
阅题
生成博客二代
珍藏网站
gcc内建函数
数学公式
hzwer
桌面高清背景图片
友链
yg
zwg
wly
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)
博主蒟蒻 可以随意转载 但要附上本文链接
广告位招租