一.题目链接：
POJ-2566
二.题目大意：
有 n 个数，编号为 a[1], a[2] ... a[n].
m 次询问，每次询问给出一个整数 t.
确定一个区间 [l, r]，使得 最小.
并输出最小值即对应区间.
三.分析：
记序列 a 的前缀和为 sum，则问题转化为求区间 [l, r] 使得 取最小值.
我们可以对 sum 排序，同时记录 sum 的原始编号.
面对这样的问题求最小值，采用尺取法即可.
四.代码实现：
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int M = (int)1e5;
const int inf = 0x3f3f3f3f;
pair <int, int> sum[M + 5];
int main()
{
int n, m, t;
while(~scanf("%d %d", &n, &m) && (n + m))
{
sum[0].first = sum[0].second = 0;
for(int i = 1; i <= n; ++i)
{
scanf("%d", &t);
sum[i].first = sum[i - 1].first + t;
sum[i].second = i;
}
sort(sum, sum + n + 1);
while((m--) > 0)
{
scanf("%d", &t);
int l = 0, r = 1;
int ans, ansl, ansr, d, dans = inf;
while(r <= n && dans)
{
int d = sum[r].first - sum[l].first;
if((int)abs(d - t) < dans)
{
ans = d;
dans = (int)abs(d - t);
ansl = sum[l].second;
ansr = sum[r].second;
}
if(d > t) ++l;
else ++r;
if(l == r) ++r;
}
if(ansl > ansr)
swap(ansl, ansr);
printf("%d %d %d\n", ans, ansl + 1, ansr);
}
}
return 0;
}
