poj 2566 Bound Found

Bound Found

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 3391		Accepted: 1042		Special Judge

Description

Signals of most probably extra-terrestrial origin have been received and digitalized by The Aeronautic and Space Administration (that must be going through a defiant phase: "But I want to use feet, not meters!"). Each signal seems to come in two parts: a sequence of n integer values and a non-negative integer t. We'll not go into details, but researchers found out that a signal encodes two integer values. These can be found as the lower and upper bound of a subrange of the sequence whose absolute value of its sum is closest to t.

You are given the sequence of n integers and the non-negative target t. You are to find a non-empty range of the sequence (i.e. a continuous subsequence) and output its lower index l and its upper index u. The absolute value of the sum of the values of the sequence from the l-th to the u-th element (inclusive) must be at least as close to t as the absolute value of the sum of any other non-empty range.

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

题意：给定一条长度为N的数列，以及值t，现在需要从数列中找到一段连续的子序列，使得该子序列中元素的总和的绝对值与t值最为接近。
思路：我们可以先计算从数列第一个元素开始一直到第i个元素为止的总和，不妨用accumulation[i]来记录，那么任意的子序列[i,j]的总和sum可以计算为accumulation[j]-accumulation[i-1].
现在可以将accumulation数组进行从小到大排序，并定义left,right为排好序数组的所要截取的子序列的左右边界，并且sum=accumulation[right]-accumulation[left].那么随着right的增大,
sum也会增大，随着left的增大，sum会减小，此时就可使用尺取法，不断改变左右边界，找到最接近t的sum值。
AC代码：

#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
#include<numeric>
#include<cmath>
using namespace std;
const int N_MAX = 100000+4;
int n, k,t, a[N_MAX];
pair<int, int>accumulation[N_MAX];//sum<->index
int get_sum(const int&t,const int &l,const int &r,int &from,int &to,int &result) {
    if (r <= l)return INT_MIN;//产生错误，返回!!!!!!
    int sum = accumulation[r].first - accumulation[l].first;
    if (abs(t-sum)<abs(t-result)) {
        result = sum;
        from = min(accumulation[r].second,accumulation[l].second);
        to = max(accumulation[r].second, accumulation[l].second);
    }
    return sum;
}

int main() {
    while (scanf("%d%d",&n,&k)&&n) {
        for (int i = 0; i < n;i++) {
            scanf("%d",&a[i]);
        }
        accumulation[0] = make_pair(0, 0);
        for (int i = 0; i < n; i++) {
            accumulation[i + 1] = make_pair(accumulation[i].first + a[i],i+1);//防止下标搞错
        }
        sort(accumulation, accumulation + n+1);//对累积和进行排序!!!!!
        while (k--) {
            scanf("%d",&t);
            int l = 0, r = 0,sum=INT_MIN,from,to,result=INT_MAX;//!!!!!
            for (;;) {
                     while(r<n&&sum<t) { 
                        sum=get_sum(t,l,++r,from,to,result);//移动右端点!!!!
                    }
                     if (sum < t) {
                         break;
                     }
                     sum = get_sum(t,++l,r,from,to,result);//移动左端点!!!!
                }
            printf("%d %d %d
",result,from+1,to);////!!!!
        }
    }
    return 0;
}