题意
给出一个整数列，求一段子序列之和最接近所给出的t。输出该段子序列之和及左右端点。
Input
The input file contains several test cases. Each test case starts with two numbers n and k. Input is terminated by n=k=0. Otherwise, 1<=n<=100000 and there follow n integers with absolute values <=10000 which constitute the sequence. Then follow k queries for this sequence. Each query is a target t with 0<=t<=1000000000.
Output
For each query output 3 numbers on a line: some closest absolute sum and the lower and upper indices of some range where this absolute sum is achieved. Possible indices start with 1 and go up to n.
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
分析
这道题可以看得出来是要用尺取法，尺取法的关键是要找到单调性。而序列时正时负，显然是不满足单调性的。
如果记录下前缀和，并排好序，这样就满足单调性了，就可以使用前缀和了
代码
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RG register int
#define rep(i,a,b) for(RG i=a;i<=b;++i)
#define per(i,a,b) for(RG i=a;i>=b;--i)
#define ll long long
#define inf (1<<30)
#define maxn 100005
using namespace std;
int n,k;
int num[maxn];
struct P{
int id,s;
inline int operator < (const P &a)const{
return s==a.s?id<a.id:s<a.s;
}
}p[maxn];
inline int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} void solve()
{
int aim=read();
int l=,r=,mn=inf,al,ar,ans;
while(l<=n&&r<=n&&mn)
{
int cal=p[r].s-p[l].s;
if(abs(cal-aim)<mn)
{
mn=abs(cal-aim);
al=p[r].id,ar=p[l].id,ans=cal;
}
if(cal>aim) ++l;
else if(cal<aim) ++r;
else break;
if(l==r) ++r;
}
if(al>ar) swap(al,ar);
printf("%d %d %d\n",ans,al+,ar);
} int main()
{
while()
{
n=read(),k=read();
if(!n&&!k) return ;
rep(i,,n) num[i]=read();
p[]=(P){,};
rep(i,,n) p[i].s=p[i-].s+num[i],p[i].id=i;
sort(p,p++n);
rep(i,,k) solve();
}
return ;
}