尺取法

尺取法是比赛中一个很有意思的技巧。
尺取法一般要保证数列的单调性才能使用。

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;
}