poj 2566 Bound Found (前缀和,尺取法(two pointer))

2015年9月24日 0 作者 CrazyKK

题意 :给定一个长度为n的区间.然后给k次询问,每次一个数t,求一个区间[l,r]使得这个区间和的绝对值最接近t

没办法直接尺取.

先预处理出来前缀和

如果要找一对区间的和的绝对值最最近t

等价于找到两个数i和j,使得sum[i]-sum[j]的绝对值最接近t,且i<>j

那么对前缀和排序…然后尺取

因为答案要输出下标

所以之前先存一下下标.

然后对于i,j

所对应的区间为[min(pre[i].id,pre[j].id)+1,max(pre[i],id,pre[j].id)];