POJ2566 – Bound Found(尺取法)

Bound Found

【题意】找一个连续的子区间，使它的和的绝对值最接近k

【分析】首先尺取法需要序列满足单调性，但是这里的前缀和并不满足单调性。但是这里是求绝对值，这样的话可以给前缀数组sum排序.

因为序列绝对值abs(sum[ed]-sum[st])==abs(sum[st]-sum[ed]).

但是需要取前缀和，单个数字排序就无法获得连续序列了。然后对接近k的条件，需要把左右两个指针都随时移动(以前写的都是枚举末尾，移动左指针，这是单调队列的思想，这里不适用)。

【AC CODE】63ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 100000+10;
struct NODE{
	int v,id;
	bool operator<(const NODE &t)const{
		return v < t.v;
	}
}p[MAXN];
int a[MAXN];

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n,q;
	while(~scanf("%d %d", &n, &q) && n+q)
	{
		p[0].v = p[0].id = 0;
		repe(i,1,n) scanf("%d", &a[i]),p[i].id = i,p[i].v = p[i-1].v+a[i];
		sort(p,p+1+n);
		while(q--)
		{
			int k;
			scanf("%d", &k);
			int ans = -1,x,y,mi = INF, st = 0, ed = 1;
			while(st <= n && ed <= n)
			{
				int sum = p[ed].v-p[st].v;
				if(abs(sum-k) < mi)
				{
					mi = abs(sum-k);
					ans = sum;
					x = p[st].id,y = p[ed].id;
				}
				if(sum < k) ed++;
				else if(sum > k) st++;
				else break;
				if(st == ed) ed++;
			}
			if(x > y)swap(x,y);
			printf("%d %d %d\n",ans,x+1,y);
		}
	}
	return 0;
}