尺取法是比赛中一个很有意思的技巧。
尺取法一般要保证数列的单调性才能使用。
while(r<=n){
if(){l++}
else{r++}
}
(POJ - 2566)Bound Found
尺取法好题，里面有尺取法的常规套路和前缀和思想。
题意：给你一个整数列和一个数x，然后求出子子段，使得子段的和的绝对值（the absolute value）最接近x。
分析：给你的整数列是可正可负的，不能直接用尺取法，所以我们必须做转换，找到单调性。但是原数列是不能动，所以可以用前缀和，加入<0,0>这个点(一上床就懂了== 理由很简单，如果我不加入零点，那么我就无法求得从第一个点到后续任一一个点的和)当然同时要记住该和是从sum[r].second-sum[l].second这一段的。
注意一下if的判断即可，最后一个l==r是说明序列为空了。
#include<bits/stdc++.h>
#define ll long long
#define CLR(x) memset(x,0,sizeof(x))
const int maxn = 100000+100;
using namespace std;
int num[maxn];
pair<int,int>sum[maxn];
void Solve()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF && n+k){
sum[0]=make_pair(0,0);
for(int i=1;i<=n;i++){
scanf("%d",&sum[i].first);
sum[i].first+=sum[i-1].first;
sum[i].second=i;
}
sort(sum,sum+1+n);
while(k--){
int x;
scanf("%d",&x);
int al, ar;
int l=0;
int r=1;
int res=INF;
int ans;
while(r<=n&&res){
int tmp=sum[r].first-sum[l].first;
if(abs(tmp-x)<res){
res=abs(tmp-x);
ans=tmp;
al=sum[l].second;
ar=sum[r].second;
}
if(tmp<x) r++;
if(tmp>x) l++;
if(l==r) r++;
}
printf("%d %d %d\n",ans,min(al,ar)+1,max(al,ar));
}
}
}
int main()
{
//FILEIN
//FILEOUT
//std::ios::sync_with_stdio(false);
int Case=1,cases;
//scanf("%d", &Case); cases=Case;
while(Case--){
//printf("Case #%d:",cases-Case);
Solve();
}
return 0;
}
