poj 2566Bound Found(前缀和，尺取法)

V2AS问路

poj 2566Bound Found(前缀和，尺取法)

阅读原文时间：2023年07月09日阅读：3

http://poj.org/problem?id=2566；

Bound Found

Time Limit: 5000MS

Memory Limit: 65536K

Total Submissions: 2237

Accepted: 692

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

Source

Ulm Local 2001

题意：找连续的串，求和绝对值与所给数字最接近的串。

思路：先求下标为1的到其他下的串的值，也就是前缀和；这样可以在O(1)的时间内求出各个串的和.比如S1(1,1),S3(1,3);

那么S3-S1就是S（2，3）；

然后对上面所求的前缀和按从小到大排序。（因为取的是绝对值所以abs(Sn-Sk)==abs(Sk-Sn)）;

这样就可以用尺取法去做了。复杂度为O(n);

还可以用二分取找值，复杂度为O(n*log(n));

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 int cmp(const void*p,const void*q);
10 typedef struct pp
11 {
12 int cost ;
13 int x;
14 int y;
15 } ss;
16 const int N=1<<30; 17 const int M=1e6; 18 int a[M]; 19 int b[M]; 20 ss dp[M]; 21 using namespace std; 22 int main(void) 23 { 24 int n,i,j,k,p,q; 25 while(scanf("%d %d",&p,&q),p!=0&&q!=0) 26 { 27 for(i=1; i<=p; i++) 28 { 29 scanf("%d",&a[i]); 30 } 31 dp[1].cost=a[1]; 32 dp[1].x=1; 33 dp[1].y=1; 34 for(i=2; i<=p; i++) 35 { 36 dp[i].cost=a[i]+dp[i-1].cost; 37 dp[i].x=1; 38 dp[i].y=i; 39 } 40 qsort(dp+1,p,sizeof(ss),cmp); 41 while(q--) 42 { 43 scanf("%d",&k); 44 int ll=1; 45 int rr=1; 46 int minn=N; 47 int lb; 48 int rb; 49 int co; 50 for(i=1; i<=p; i++) 51 { 52 if(abs(abs(dp[i].cost)-k)k&&rr-ll>1)
71 {
72 int nx=abs(abs(dp[rr].cost-dp[ll].cost)-k);
73 int ny=abs(abs(dp[rr-1].cost-dp[ll].cost)-k);
74 int kl=rr;
75 if(nyk&&rr-ll==1)
88 {
89 if(abs(abs(dp[rr].cost-dp[ll].cost)-k)cost==w->cost)
120 {
121 return ww->y-w->y;
122 }
123 return ww->cost-w->cost;
124 }

二分

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 const int N=1000000;
9 int cmp(const void*p,const void*q);
10 int er(int n,int m,int t,int c);
11 typedef struct pp
12 {
13 int cost;
14 int le;
15 int ri;
16 } ss;//结构体记录前缀数组和和其左右端点
17 ss a[N];
18 int b[N],c[N];
19 int vv;
20 using namespace std;
21 int main(void)
22 {
23 int n,i,j,k,p,q;
24 while(scanf("%d %d",&p,&q),p!=0&&q!=0)
25 {
26 for(i=1; i<=p; i++) 27 scanf("%d",&b[i]); 28 int cnt=1; 29 a[cnt].cost=b[1]; 30 a[cnt].le=1; 31 a[cnt].ri=1; 32 cnt++; 33 for(i=2; i<=p; i++) 34 { 35 a[cnt].cost=a[cnt-1].cost+b[i]; 36 a[cnt].le=1; 37 a[cnt].ri=i; 38 cnt++; 39 } 40 qsort(a+1,cnt-1,sizeof(ss),cmp); 41 /*for(i=1;i<=p;i++) 42 { 43 printf("%d\n",a[i].cost); 44 printf("000\n"); 45 printf("%d\n",a[i].ri); 46 }*/ 47 for(i=1; i<=q; i++) 48 { 49 cin>>b[i];
50 }
51 for(int pq=1; pq<=q; pq++) 52 { 53 k=b[pq]; 54 int minn=1<<30; 55 int ll=0; 56 int rr=0; 57 int uk=0; 58 for(j=1; j<=p; j++) 59 { 60 if(abs(abs(a[j].cost)-k)1)//这里需要判断下，kk-vv>1才能用下面的比较。
74 {int uu=abs(abs(a[kk-1].cost-a[j].cost)-k);
75 int w=abs(abs(a[kk].cost-a[j].cost)-k);
76 if(uucost-ww->cost;
133 }
134 int er(int n,int m,int k,int c)
135 {
136 int y=(n+m)/2;
137 if(abs(a[y].cost-a[c].cost)==k)
138 {
139 return y;
140 }
141 else if(n==m)
142 {
143 return m;
144 }
145 else if(abs(a[y].cost-a[c].cost)>k&&abs(a[y-1].cost-a[c].cost)<k)
146 {
147 return y;
148 }
149 else if(abs(a[y].cost-a[c].cost)<k&&abs(a[y-1].cost-a[c].cost)<k)
150 {
151 return er(y+1,m,k,c);
152 }
153 else return er(n,y-1,k,c);
154 }

手机扫一扫

移动阅读更方便

你可能感兴趣的文章