POJ 2566(尺取法

自己看了半天并没有看出这题怎么用尺取法（虽然一看就觉得肯定是尺取法。。），由于是绝对值，那么在计算的时候头和尾的实际位置并不重要，而应用尺取法这个数列肯定得是单调，那么我们把前缀和处理出来排序就可以直接应用尺取法了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#define INF 0x3fffffff
#define pb push_back
#define pn(x) cerr<<x<<endl

using namespace std;
typedef long long ll;
const int maxv=1e5+20;
typedef pair<ll,ll> P;///pfx,pos
int n,k,t;
ll a[maxv];
P pfx[maxv];
void get_pfx(){
    pfx[0].first=pfx[0].second=0;
    for(int i=1;i<=n;i++){
        pfx[i].first=pfx[i-1].first+a[i];
        pfx[i].second=i;
    }
    sort(pfx,pfx+n+1);
}
int main(){
    ///freopen("in.txt","r",stdin);
    while(cin>>n>>k){
        if(n==0&&k==0) break;
        for(int i=1;i<=n;i++) scanf("%I64d",&a[i]);
        get_pfx();
        while(k--){
            cin>>t;
            ll minn=1e17,ans;
            int l=0,r=0;
            int al=0,ar=0;
            while(l<n&&r<=n){
                if(l==r){
                    r++;
                    continue;
                }
                ll val=abs(pfx[r].first-pfx[l].first);
                if(abs(val-t)<minn){
                    minn=abs(val-t);
                    ans=val;
                    al=pfx[l].second;
                    ar=pfx[r].second;
                }
                else if(val<t) r++;
                else l++;
            }
            if(al>ar) swap(al,ar);
            cout<<ans<<" "<<al+1<<" "<<ar<<endl;
        }
    }
    return 0;
}