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 }

  

参考http://www.hankcs.com/program/algorithm/poj-2566-bound-found.html

时间: 01-23

Greedy:Bound Found(POJ 2566)的相关文章

挑战程序设计竞赛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(尺取法+前缀和)

题目链接:http://poj.org/problem?id=2566 题意:给定一个序列(n个整数)和一个整数k(m个),求出这个序列的一个子串,使之和的绝对值与k的差最小. 尺取法的题目有两个特性: 1. 所求的序列是一个连续的序列,这样才能将序列抽象成一个头和一个尾来描述. 2. 头尾枚举的序列满足某种单调的性质,这样才能进行尺取的操作. 这个序列是一个随意的序列,不可能直接对其进行操作,先要预处理下,进行前缀和操作,把对应的值和标记放在同一个pair. 然后根据前缀和的值进行排序,这样就

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

题意:询问一个静态序列的连续区间和绝对值最接近t的下标. 分析:由于询问的是绝对值,可以用前缀和相减得到区间和,并且和位置前后没有关系.于是把记录下标信息以后把 前缀和排序枚举大的前缀pj,pj-pi ≍ t,满足条件的:有pj-t的plower_bound以及plower_bound-1. 而pj-t也是单调的,再用一个下标i去维护就好. /********************************************************* * -----------------

Greedy:Cow Acrobats(POJ 3045)

牛杂技团 题目大意:一群牛想逃跑,他们想通过搭牛梯来通过,现在定义risk(注意可是负的)为当前牛上面的牛的总重量-当前牛的strength,问应该怎么排列才能使risk最小? 说实话这道题我一开始给书上的二分法给弄懵了,后来看了一下题解发现根本不是这么一回事,其实就是个简单的贪心法而已. 这题怎么贪心呢?就是按w+s从小到大排序就好了,证明一下: 1.先证明如果不满足w+s的序列性,无论谁在谁的上面,都会违反题设:(设A在B的上面) 如果 A.s+A.w<B.s+B.w 则如果B.s<m+A

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