POJ 2566 Bound Found 题解 《挑战程序设计竞赛》

POJ 2566 Bound Found

上下界：从数列中找出连续序列，使得和的绝对值与目标数之差最小。

3.2常用技巧精选（一）

尺取法

因为前缀和不单调，所以需要先排个序。之后就是尺取法了：首尾分别逐步向前挪动，挪动过程中记录答案。找了半天尺取虫的图片，还是卡通的容易接受一点，其他太惊悚。另外以后ACM相关的文章放到算法分类下，不在放到C++里了。

#include <iostream>
#include <algorithm>

using namespace std;
#define MAX_N 100000 + 16
int a[MAX_N];
pair<int, int> accumulation[MAX_N];	// sum <-> index

// 更新答案
int get_sum(int& result, const int& l, const int& r, const int& t, int& from, int& to)
{
	if (l >= r)
	{
		return INT_MIN;	// 不合法，终止
	}
	int sum = accumulation[r].first - accumulation[l].first;
	if (abs(t - sum) < abs(t - result))	// 顺便记录一下可能的答案
	{
		result = sum;
		from = min(accumulation[l].second, accumulation[r].second);
		to = max(accumulation[l].second, accumulation[r].second);
	}
	return sum;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n, k;
	while (cin >> n >> k && n)
	{
		for (int i = 0; i < n; ++i)
		{
			cin >> a[i];
		}
		accumulation[0] = make_pair(0, 0);	// 多留一个，待会儿免得下标跟答案对不上
		for (int i = 0; i < n; ++i)
		{
			accumulation[i + 1] = make_pair(accumulation[i].first + a[i], i + 1);
		}
		sort(accumulation, accumulation + n + 1);
		while (k--)
		{
			int t;
			cin >> t;
			// 输入结束
			int l = 0, r = 0, sum = 0x80808080, from, to, result = 0x80808080;
			for (;;)
			{
				while (r < n && sum < t)
				{
					sum = get_sum(result, l, ++r, t, from, to);	// ++r 头部前进
				}
				if (sum < t)
				{
					break;
				}

				sum = get_sum(result, ++l, r, t, from, to);	// ++l 尾部前进
			}
			cout << result << ' ' << from + 1 << ' ' << to << endl;
		}
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2566 Bound Found 题解 《挑战程序设计竞赛》