Greedy:Bound Found(POJ 2566)

                Greedy:Bound Found(POJ 2566)

                    神奇密码

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

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

  

 #include <iostream>
#include <algorithm>
#include <functional> using namespace std; //pair<int, int>Acc[100016];
static struct _set
{
int sum, index;
bool operator<(const _set&x)const
{
return sum < x.sum;
}
}Acc[]; void solve(const int, const int);
int get_sum(int *const, int*const, int*const, const int, const int,const int);
int ABS(int); int main(void)//游标卡尺大法
{
int n, k, t, tmp; while (~scanf("%d%d", &n, &k))
{
if (n == && k == )
break;
Acc[].sum = ; Acc[].index = ;
for (int i = ; i <= n; i++)
{
scanf("%d", &tmp);
Acc[i].index = i; Acc[i].sum = Acc[i - ].sum + tmp;
}
sort(Acc, Acc + n + );//直接给和排序 for (int i = ; i < k; i++)
{
scanf("%d", &t);
solve(n, t);
}
}
return ;
} void solve(const int n, const int S)
{
int ans_sum, ans_lb, ans_ub, lb, ub, sum; lb = ub = ; sum = ans_sum = 0x80808080;
while ()
{
while (ub < n && sum < S)//标准尺取法
sum = get_sum(&ans_sum, &ans_lb, &ans_ub, lb, ++ub, S);
if (sum < S)
break;
sum = get_sum(&ans_sum, &ans_lb, &ans_ub, ++lb, ub, S);
}
printf("%d %d %d\n", ans_sum, ans_lb + , ans_ub);
} int ABS(int x)
{
return x >= ? x : -x;
} int get_sum(int *const ans_sum, int*const ans_lb, int*const ans_ub, const int lb, const int ub,const int S)
{
if (lb >= ub)
return INT_MIN;
int tmp = Acc[ub].sum - Acc[lb].sum;
if (ABS(tmp - S) < ABS(*ans_sum - S))
{
*ans_sum = tmp;
*ans_lb = min(Acc[ub].index, Acc[lb].index);
*ans_ub = max(Acc[ub].index, Acc[lb].index);
}
return tmp;
}

  Greedy:Bound Found(POJ 2566)

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

上一篇:【转】struts2.5框架使用通配符指定方法(常见错误)


下一篇:struts2.5框架使用通配符指定方法,某一个匹配不到