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.
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
上下界：从数列中找出连续序列，使得和的绝对值与目标数之差最小。
从数列中找出连续序列，使得和的绝对值与目标数之差最小
因为前缀和不单调，所以需要先排个序，之后就是尺取法了:首尾分别逐步向前挪动，挪动过程中记录答案
3.2常用技巧精选（一）
尺取法
因为前缀和不单调，所以需要先排个序。之后就是尺取法了：首尾分别逐步向前挪动，挪动过程中记录答案
http://blog.csdn.net/wiking__acm/article/details/9910415题意就是找一个连续的子区间，使它的和的绝对值最接近target。这题的做法是先预处理出前缀和，然后对前缀和进行排序，再用尺取法贪心的去找最合适的区间，要注意的是尺取法时首尾指针一定不能相同，因为这时区间相减结果为0，但实际上区间为空，这是不存在的，可能会产生错误的结果。处理时，把（0,0）这个点也放进数组一起排序，比单独判断起点为1的区间更方便。还有ans初始化的值INF一定要大于t的最大值。最后说说这个题最重要的突破口，对前缀和排序。为什么这么做是对的呢？以为这题是取区间的和的绝对值，所以所以用sum[r]-sum[l] 和 sum[l]-sum[r]是没有区别的。这样排序后，把原来无序的前缀和变成有序的了，就便于枚举的处理，并且不影响最终结果。
题意：对一个长度为n的数列，做k次查询，每次查询一个数t，求原数列中的一个子区间[l, r]，使得该子区间的和的绝对值最接近t。
思路：在原数列开头添加一个0，处理好现数列a[N]的前缀和pre[N]。则原问题转化为在前缀数组中求2个数pre[i]，pre[j]的差的绝对值最接近t的。对于每次找到的2个下标分别为i和j的2个数，所对应a的区间为[min(i, j) + 1, max(i, j)]。
那么将前缀和数组排序后，即可用尺取法得到最接近的值。
注意的是：排序时需要保留原来的下标值，以便于求区间。
尺取法的一般用法就是对于一个连续区间求解某些最值，此题便是如此
因为前缀和不单调，所以需要先排序。在原数组开头添加0，求出前缀数组。题目即转化为在前缀数组中找pre[i]，pre[j]，两者之差最接近t，。对于每次找到的2个下标分别为i和j的2个数，所对应a的区间为[min(i, j) + 1, max(i, j)]。
那么前缀数组排序后，尺取法便可以求得最接近t的值。
首先求前缀和。由于是绝对值与t比较，所以左右断点交换没有影响，故可以将求好的前缀和排序。
然后用尺取法。如果当前区间各个数和的绝对值小于ans则更新。
比较 当前区间各个数的和 与t的大小 改变区间的左右端点。
比t大，则左端点++ ； 否则，右端点++。
- typedef pair<int, int> P;
- typedef long long LL;
- P p[maxn];
- int Abs(int x){return x<0?-x:x;}
- int n;
- void query(int tar){
- int s = 0,e = 1,Min = INF;
- int ansl,ansr,ansx;
- while(s <= n && e <= n){
- int tem = p[e].first-p[s].first;
- if(Abs(tem-tar) < Min){
- Min = Abs(tem-tar);
- ansx = tem;
- ansl = p[s].second;
- ansr = p[e].second;
- }
- if(tem > tar) s++;
- else if(tem < tar) e++;
- else break;
- if(s == e) e++;
- }
- if(ansl > ansr) swap(ansl,ansr);
- printf("%d %d %d\n",ansx,ansl+1,ansr);
- }
- int main(){
- int m;
- while(scanf("%d%d",&n,&m)){
- if(n == 0 && m == 0) break;
- p[0] = P(0,0);
- int sum = 0;
- for(int i = 1;i <= n;i++){
- int tem;
- scanf("%d",&tem);
- sum += tem;
- p[i] = P(sum,i);
- }
- sort(p,p+n+1);
- while(m--){
- int x;
- scanf("%d",&x);
- query(x);
- }
- }
- return 0;
- }
int a[MAX_N];pair<int, int> accumulation[MAX_N]; // sum <-> index// 更新答案int get_sum(int& result, const int& l, const int& r, const int& t, int& from, int& to){ if (l >= r) { return INT_MIN; // 不合法，终止 } int sum = accumulation[r].first - accumulation[l].first; if (abs(t - sum) < abs(t - result)) // 顺便记录一下可能的答案 { result = sum; from = min(accumulation[l].second, accumulation[r].second); to = max(accumulation[l].second, accumulation[r].second); } return sum;}///////////////////////////SubMain//////////////////////////////////int main(int argc, char *argv[]){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif int n, k; while (cin >> n >> k && n) { for (int i = 0; i < n; ++i) { cin >> 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--) { int t; cin >> t; // 输入结束 int l = 0, r = 0, sum = 0x80808080, from, to, result = 0x80808080; for (;;) { while (r < n && sum < t) { sum = get_sum(result, l, ++r, t, from, to); // ++r 头部前进 } if (sum < t) { break; } sum = get_sum(result, ++l, r, t, from, to); // ++l 尾部前进 } cout << result << ' ' << from + 1 << ' ' << to << endl; } }#ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt");#endif return 0;}pair<int,int> P[maxn];
void solve(int x)
{
int l=0,r=1,Min=INF;
int ansx,ansl,ansr;
while(l<=n&&r<=n)
{
int y=P[r].first-P[l].first;
if(abs(y-x)<Min)//更新差值的最小值
{
Min=abs(y-x);
ansx=y;
ansl=P[l].second;
ansr=P[r].second;
}
if(y<x) r++;//小于目标值右标前进
else if(y>x) l++;//大于目标值左标前进
else break;//等于目标值退出循环
if(l==r)//左右标相同则右标前进
r++;
}
if(ansl>ansr)//左标必须小于等于右标
swap(ansl,ansr);
printf("%d %d %d\n",ansx,ansl+1,ansr);
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0)
break;
P[0]=pair<int,int>(0,0);
int d,sum=0;
for(int i=1;i<=n;++i)
{
scanf("%d",&d);
sum+=d;//前缀和
P[i]=pair<int,int>(sum,i);
}
sort(P,P+n+1);//对前缀和排序
while(m--)//m次查询
{
int x;
scanf("%d",&x);
solve(x);
}
}
return 0;
}
Read full article from POJ 2566 Bound Found 题解 《挑战程序设计竞赛》 � 码农场
