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}

相关文章