# Greedy:Bound Found(POJ 2566)

题目大意：就是给你一个数组，要你找出连续的数的绝对值的和最接近t的那一串，并且要找出数组的上界和下界的下标，并显示他们的和

因为这一题的数有正有负，所以必须要先把和求出来，然后排序，然后利用a(s,t)=sum(t)-sum(s)找出目标

``` 1 #include <iostream>
2 #include <algorithm>
3 #include <functional>
4
5 using namespace std;
6
7 //pair<int, int>Acc[100016];
8 static struct _set
9 {
10     int sum, index;
11     bool operator<(const _set&x)const
12     {
13         return sum < x.sum;
14     }
15 }Acc[100002];
16
17 void solve(const int, const int);
18 int get_sum(int *const, int*const, int*const, const int, const int,const int);
19 int ABS(int);
20
21 int main(void)//游标卡尺大法
22 {
23     int n, k, t, tmp;
24
25     while (~scanf("%d%d", &n, &k))
26     {
27         if (n == 0 && k == 0)
28             break;
29         Acc[0].sum = 0; Acc[0].index = 0;
30         for (int i = 1; i <= n; i++)
31         {
32             scanf("%d", &tmp);
33             Acc[i].index = i; Acc[i].sum = Acc[i - 1].sum + tmp;
34         }
35         sort(Acc, Acc + n + 1);//直接给和排序
36
37         for (int i = 0; i < k; i++)
38         {
39             scanf("%d", &t);
40             solve(n, t);
41         }
42     }
43     return 0;
44 }
45
46 void solve(const int n, const int S)
47 {
48     int ans_sum, ans_lb, ans_ub, lb, ub, sum;
49
50     lb = ub = 0; sum = ans_sum = 0x80808080;
51     while (1)
52     {
53         while (ub < n && sum < S)//标准尺取法
54             sum = get_sum(&ans_sum, &ans_lb, &ans_ub, lb, ++ub, S);
55         if (sum < S)
56             break;
57         sum = get_sum(&ans_sum, &ans_lb, &ans_ub, ++lb, ub, S);
58     }
59     printf("%d %d %d\n", ans_sum, ans_lb + 1, ans_ub);
60 }
61
62 int ABS(int x)
63 {
64     return x >= 0 ? x : -x;
65 }
66
67 int get_sum(int *const ans_sum, int*const ans_lb, int*const ans_ub, const int lb, const int ub,const int S)
68 {
69     if (lb >= ub)
70         return INT_MIN;
71     int tmp = Acc[ub].sum - Acc[lb].sum;
72     if (ABS(tmp - S) < ABS(*ans_sum - S))
73     {
74         *ans_sum = tmp;
75         *ans_lb = min(Acc[ub].index, Acc[lb].index);
76         *ans_ub = max(Acc[ub].index, Acc[lb].index);
77     }
78     return tmp;
79 }```

## 挑战程序设计竞赛3.2习题：Bound Found POJ - 2566

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

## poj 2566 Bound Found (前缀和，尺取法（two pointer）)

Bound Found Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 2010   Accepted: 659   Special Judge Description Signals of most probably extra-terrestrial origin have been received and digitalized by The Aeronautic and Space Administration

## POJ 2566：Bound Found（Two pointers）

[题目链接] http://poj.org/problem?id=2566 [题目大意] 给出一个序列,求一个子段和,使得其绝对值最接近给出值, 输出这个区间的左右端点和区间和. [题解] 因为原序列的前缀和不具有单调性,难以处理, 因此我们对前缀和进行排序,同时保留前缀和的右端点做标识作用, 题目要求区段和的绝对值最接近目标,因此排序不会造成前后顺序变化造成的影响 现在题目转化为在一个有序数列中,求一个数对,使得差值最接近给出数, 利用单调性,可以尺取解决问题. [代码] #include <

## poj 2566 Bound Found 尺取法 变形

Bound Found Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 2277   Accepted: 703   Special Judge Description Signals of most probably extra-terrestrial origin have been received and digitalized by The Aeronautic and Space Administration

## poj 2566 Bound Found（尺取法 好题）

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

## POJ 2566 尺取法（进阶题）

Bound Found Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 4297   Accepted: 1351   Special Judge Description Signals of most probably extra-terrestrial origin have been received and digitalized by The Aeronautic and Space Administration