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

题意 :给定一个长度为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)];

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz