POJ-2566-Bound Found(尺取法 好题！！！)

题目
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

题意:给你一个序列长度n。再给一个q次询问。然后有n个数代表ai(里面的数是任意整数,不一定正负)。接下来给q个t。让你输出一个区间。使得 | 区间和 | 与 t 最接近。
也就是| |区间和|- t |最小。
思路：yeah！
这个题有负数。有负数。有负数。不满足尺取法的要求。但是他是区间和的绝对值。区间和一般可以转化为 前缀和做差。既然是绝对值。那么前缀和可以排个序？！哈哈哈。后面的减前面的。得到的就是正数，就是一段区间的绝对值了。既然排序是否满足单调性？？很可能！！那我们就来看一下是否满足尺取的性质？？。见下图。

[l,r]最优时，[ll,rr]不可能最优(l<ll,rr<r)。画个图就知道了。
当当前情况>t时,l++。小于t时,r++。等于t时break。就在那里来回晃荡寻找就行了。支持他的理论依据就是，他不会错过优的区间。
比如>t时,此时假如 l 不变的话,r++有个屁用，都已经>t了还想更大吗。
就不要枚举[l,k]（k>r）这些了，因为显然显然不可能把。然后就右移 l 。显然少枚举了[ll,rr]因为右移后,r从当前位置移动而不是回到左端点重新枚举。这些区间的不是最优性已经证明。
这两种尺取思想一样。可以用这样的代码写，但是感觉(l==r)时很不好处理。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define m(a,b) memset(a,b,sizeof a)
#define en '\n'
using namespace std;
typedef long long ll;
const int N=1e5+2,M=1e5+2,INF=0x3f3f3f3f;
struct node{ll sum;int id;}a[N];
bool cmp(node x,node y) {return x.sum<y.sum;}
ll myabs(ll x) {return x>0?x:-x;}
int main()
{
    int n,q;
    while(~scanf("%d%d",&n,&q),n||q)
    {
        a[0]=(node){0,0};//这个要放在最开始!!! {0,0}放进去就是因为谁(x)减这个,就代表区间[1,x].
        int x;
        for(int i=1;i<=n;i++)
            scanf("%d",&x),a[i].sum=a[i-1].sum+x,a[i].id=i;
        sort(a,a+n+1,cmp);
        while(q--)
        {
            ll t;scanf("%lld",&t);
            int l=0,r=1,tl,tr;ll tsum,ans=INF;
            while(r<=n)//另一种类型的尺取
            {
                ll tmp=a[r].sum-a[l].sum,anss;
                if((anss=myabs(tmp-t))<ans)
                {
                    ans=anss;
                    tsum=tmp;
                    tl=a[l].id,tr=a[r].id;
                }
                if(tmp==t) break;
                if(tmp<t) r++;
                if(tmp>t) l++;
                if(l==r) r++;(因为l==r时,区间长度为0了,么的枚举了)
            }
            if(tl>tr) swap(tl,tr);
            printf("%lld %d %d\n",tsum,tl+1,tr);
        }
    }
}