题目描述
Signals of most probably extra-terrestrial origin have been received and digitalized by The Aeronautic and Space Administration (that must be going through a defiant phase: “But I want to use feet, not meters!”). Each signal seems to come in two parts: a sequence of n integer values and a non-negative integer t. We’ll not go into details, but researchers found out that a signal encodes two integer values. These can be found as the lower and upper bound of a subrange of the sequence whose absolute value of its sum is closest to t.
You are given the sequence of n integers and the non-negative target t. You are to find a non-empty range of the sequence (i.e. a continuous subsequence) and output its lower index l and its upper index u. The absolute value of the sum of the values of the sequence from the l-th to the u-th element (inclusive) must be at least as close to t as the absolute value of the sum of any other non-empty range.
样例
Sample Input
5 1
-10 -5 0 5 10
3
10 2
-9 8 -7 6 -5 4 -3 2 -1 0
5 11
15 2
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
15 100
0 0
Sample Output
5 4 4
5 2 8
9 1 1
15 1 15
15 1 15
算法1
(双指针) $O(nlog_2n)$
要使用双指针算法需要有单调性,但区间和并没有单调性,但如果先求前缀和,再排序就有了单调性,而区间和可以用任意两个前缀和之差求得。
指针$i,j$指向两个前缀和,差值绝对值$diff=abs(s[j]-s[i])$,由于排过序$s[j]>=s[i],diff=s[j]-s[i]$,得到区间和,若$diff\lt t,j\++$,使$diff$增大,若$diff=t$,则最接近$t$,直接结束,若$diff\gt t,i\++$。每次得到新$diff$时更新原最小值。
本题有Special Judge。
时间复杂度
双指针时间复杂度为$O(n)$,但排序时间复杂度为$O(nlog_2n)$。
Python 代码
while True:
n,k=map(int,input().split())
if n==k==0:
break
s=[0]+list(map(int,input().split()))
T=list(map(int,input().split()))
for i in range(1,n+1):
s[i]+=s[i-1]
for i in range(n+1):
s[i]=(s[i],i)
s.sort()
for i in range(k):
t=T[i]
l=0
r=1
Min=float('INF')
posl=0
posr=0
ans=0
while r<=n and l<=r:
tmp=s[r][0]-s[l][0]
if abs(tmp-t)<Min:
posl=min(s[l][1],s[r][1])+1
posr=max(s[l][1],s[r][1])
Min=abs(tmp-t)
ans=tmp
if tmp<t:
r+=1
elif tmp==t:
break
else:
l+=1
print(ans,posl,posr)