http://poj.org/problem?id=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 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 Sample Output 5 4 4 Source |
||||||||||
题意：找连续的串，求和绝对值与所给数字最接近的串。
思路：先求下标为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<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string.h>
5 #include<math.h>
6 #include<vector>
7 #include<map>
8 #include<stack>
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)<minn)
53 {
54 minn=abs(abs(dp[i].cost)-k);
55 lb=1;
56 rb=dp[i].y;
57 co=abs(abs(dp[i].cost));
58 }
59 }
60 while(rr<p)
61 {
62 while(rr<=p&&abs(dp[rr].cost-dp[ll].cost)<=k)
63 {
64 rr++;
65 }
66 if(rr==p+1)
67 {
68 rr--;
69 }
70 if(abs(dp[rr].cost-dp[ll].cost)>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(ny<nx)
76 {
77 kl--;
78 }
79 if(abs(abs(dp[kl].cost-dp[ll].cost)-k)<minn)
80 {
81 lb=min(dp[kl].y,dp[ll].y)+1;
82 rb=max(dp[kl].y,dp[ll].y);
83 minn=abs(abs(dp[kl].cost-dp[ll].cost)-k);
84 co=abs(dp[kl].cost-dp[ll].cost);
85 }
86 }
87 else if(abs(dp[rr].cost-dp[ll].cost)>k&&rr-ll==1)
88 {
89 if(abs(abs(dp[rr].cost-dp[ll].cost)-k)<minn)
90 {
91 lb=min(dp[rr].y,dp[ll].y)+1;
92 rb=max(dp[rr].y,dp[ll].y);
93 minn=abs(abs(dp[rr].cost-dp[ll].cost)-k);
94 co=abs(dp[rr].cost-dp[ll].cost);
95 }
96
97 }
98 else if(abs(dp[rr].cost-dp[ll].cost)<=k)
99 {
100 if(abs(abs(dp[rr].cost-dp[ll].cost)-k)<minn)
101 {
102 lb=min(dp[rr].y,dp[ll].y)+1;
103 rb=max(dp[rr].y,dp[ll].y);
104 minn=abs(abs(dp[rr].cost-dp[ll].cost)-k);
105 co=abs(dp[rr].cost-dp[ll].cost);
106 }
107
108 }
109 ll++;
110 }
111 printf("%d %d %d\n",co,lb,rb);
112 }
113 }
114 }
115 int cmp(const void*p,const void*q)
116 {
117 ss*ww=(ss*)p;
118 ss*w=(ss*)q;
119 if(ww->cost==w->cost)
120 {
121 return ww->y-w->y;
122 }
123 return ww->cost-w->cost;
124 }
二分
1 #include<stdio.h>
2 #include<algorithm>
3 #include<stdlib.h>
4 #include<string.h>
5 #include<algorithm>
6 #include<iostream>
7 #include<map>
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)<minn)
61 {
62 minn=abs(abs(a[j].cost)-k);
63 uk=abs(a[j].cost);
64 ll=1;
65 rr=a[j].ri;
66 }
67 }//首先把所有前缀过一遍更新最小，因为二分时找不到
68 for(j=1; j<p; j++)
69 {
70 int kk=er(j+1,p,k,j);
71 vv=j;
72 if(kk==p)
73 {if(kk-vv>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(uu<w)
77 {
78 kk--;
79 }
80 int ww=abs(abs(a[kk].cost-a[j].cost)-k);
81 if(ww<minn)
82 {
83 minn=ww;
84 ll=min(a[kk].ri,a[j].ri)+1;
85 rr=max(a[kk].ri,a[j].ri);
86 uk=abs(a[kk].cost-a[j].cost);
87 }}
88 else if(kk-vv==1)//kk-vv正好为1时表明kk就为所找，不能再比较kk-1，因为kk-1为空值
89 { int ww=abs(abs(a[kk].cost-a[j].cost)-k);
90 if(ww<minn)
91 {
92 minn=ww;
93 ll=min(a[kk].ri,a[j].ri)+1;
94 rr=max(a[kk].ri,a[j].ri);
95 uk=abs(a[kk].cost-a[j].cost);
96 }
97 }
98 }
99 else
100 {
101
102 int uu=abs(abs(a[kk-1].cost-a[j].cost)-k);
103 int w=abs(abs(a[kk].cost-a[j].cost)-k);
104 if(uu<w)
105 {
106 kk--;
107 }
108 if(kk==j)
109 {
110 kk++;
111 }
112 int ww=abs(abs(a[kk].cost-a[j].cost)-k);
113 if(ww<minn)
114 {
115 minn=ww;
116 ll=min(a[kk].ri,a[j].ri)+1;
117 rr=max(a[kk].ri,a[j].ri);
118 uk=abs(a[kk].cost-a[j].cost);
119
120 }
121 }
122
123 }
124 printf("%d %d %d\n",uk,ll,rr);
125 }
126 }
127 }
128 int cmp(const void*p,const void*q)//二分查找
129 {
130 ss*w=(ss*)p;
131 ss*ww=(ss*)q;
132 return w->cost-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 }