poj 2566 Bound Found (前缀和，尺取法（two pointer）)
题意 ：给定一个长度为n的区间．然后给k次询问，每次一个数t,求一个区间[l,r]使得这个区间和的绝对值最接近t
没办法直接尺取.
先预处理出来前缀和
如果要找一对区间的和的绝对值最最近t
等价于找到两个数i和j,使得sum[i]-sum[j]的绝对值最接近t,且i<>j
那么对前缀和排序…然后尺取
因为答案要输出下标
所以之前先存一下下标．
然后对于i，j
所对应的区间为[min(pre[i].id,pre[j].id)+1,max(pre[i],id,pre[j].id)];
1/*************************************************************************
2 > File Name: code/poj/2566.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年09月24日 星期四 22时10分08秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#include<cctype>
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define ms(a,x) memset(a,x,sizeof(a))
25#define lr dying111qqz
26using namespace std;
27#define For(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef double DB;
30const int N=1E5+7;
31const int inf = 0x3f3f3f3f;
32int a[N];
33int n ,k;
34struct Q
35{
36 int id;
37 int sum;
38}pre[N];
39
40bool cmp(Q a,Q b)
41{
42 if (a.sum<b.sum) return true;
43 if (a.sum==b.sum&&a.id<b.id) return true;
44 return false;
45}
46
47void solve ( int t)
48{
49 int ansl,ansr,ans;
50 int l = 0 ;
51 int r = 1;
52 int mi = inf;
53 while ( r<= n )
54 {
55 int tmp = pre[r].sum - pre[l].sum;
56
57 if (abs(tmp-t)<mi)
58 {
59 mi = abs(tmp-t);
60 ansl = min(pre[l].id,pre[r].id)+1;
61 ansr = max(pre[l].id,pre[r].id);
62 ans = tmp;
63 }
64 if (tmp<t)
65 {
66 r++;
67 }
68 else
69 if (tmp>t)
70 {
71 l++;
72 }
73 else break;
74
75 if (l==r) r++;
76 }
77 printf("%d %d %d\n",ans,ansl,ansr);
78}
79
80int main()
81{
82 #ifndef ONLINE_JUDGE
83 freopen("in.txt","r",stdin);
84 #endif
85 while (scanf("%d %d",&n,&k)!=EOF)
86 {
87 if (n==0&&k==0) break;
88 pre[0].id = 0 ;
89 pre[0].sum = 0 ;
90 for ( int i = 1 ; i <= n ; i++)
91 {
92 scanf("%d",&a[i]);
93 pre[i].sum = pre[i-1].sum + a[i];
94 pre[i].id = i ;
95 // cout<<pre[i].sum<<" ";
96 }
97// cout<<endl;
98
99 sort(pre,pre+n+1,cmp);
100// for ( int i = 0 ; i <= n ; i++) cout<<pre[i].sum<<" "; cout<<endl;
101 for ( int i = 1 ; i <= k ; i++)
102 {
103 int x;
104 scanf("%d",&x);
105 solve(x);
106 }
107 }
108
109 #ifndef ONLINE_JUDGE
110 fclose(stdin);
111 #endif
112 return 0;
113}