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)];
/*************************************************************************
> File Name: code/poj/2566.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年09月24日 星期四 22时10分08秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#include<cctype>
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define ms(a,x) memset(a,x,sizeof(a))
18#define lr dying111qqz
19using namespace std;
20#define For(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef double DB;
23const int N=1E5+7;
24const int inf = 0x3f3f3f3f;
25int a[N];
26int n ,k;
27struct Q
28{
29 int id;
30 int sum;
31}pre[N];
1bool cmp(Q a,Q b)
2{
3 if (a.sum<b.sum) return true;
4 if (a.sum==b.sum&&a.id<b.id) return true;
5 return false;
6}
1void solve ( int t)
2{
3 int ansl,ansr,ans;
4 int l = 0 ;
5 int r = 1;
6 int mi = inf;
7 while ( r<= n )
8 {
9 int tmp = pre[r].sum - pre[l].sum;
1 if (abs(tmp-t)<mi)
2 {
3 mi = abs(tmp-t);
4 ansl = min(pre[l].id,pre[r].id)+1;
5 ansr = max(pre[l].id,pre[r].id);
6 ans = tmp;
7 }
8 if (tmp<t)
9 {
10 r++;
11 }
12 else
13 if (tmp>t)
14 {
15 l++;
16 }
17 else break;
1 if (l==r) r++;
2 }
3 printf("%d %d %d\n",ans,ansl,ansr);
4}
1int main()
2{
3 #ifndef ONLINE_JUDGE
4 freopen("in.txt","r",stdin);
5 #endif
6 while (scanf("%d %d",&n,&k)!=EOF)
7 {
8 if (n==0&&k==0) break;
9 pre[0].id = 0 ;
10 pre[0].sum = 0 ;
11 for ( int i = 1 ; i <= n ; i++)
12 {
13 scanf("%d",&a[i]);
14 pre[i].sum = pre[i-1].sum + a[i];
15 pre[i].id = i ;
16 // cout<<pre[i].sum<<" ";
17 }
18// cout<<endl;
1 sort(pre,pre+n+1,cmp);
2// for ( int i = 0 ; i <= n ; i++) cout<<pre[i].sum<<" "; cout<<endl;
3 for ( int i = 1 ; i <= k ; i++)
4 {
5 int x;
6 scanf("%d",&x);
7 solve(x);
8 }
9 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}