POJ2566-Bound Found
题目大意：给出一个长度为N的数列，元素有正有负。求该数列和的绝对值与一个给定的数t绝对值之差最小的子段的位置。
由于题目给出了多组数据，每组数据多次询问，且没有说明数据组数与询问次数，我一直在想着找O(1)的方法来回答每次询问，想破了头都没想出来。无奈看题解，结果题解也是用O(n)的方法来回答的…
题解用了尺取的方法来写这题。在尺取中，一个基本的条件是尺取的序列上，所有起点相同的子段，终点越靠后的值越大，（即该序列是不下降的）。这题求的是区间和，第一反应肯定是用前缀和来求，但有正有负的序列前缀和不是不下降的。
然而，由于题目只关心区间和的绝对值，而∣s[i]−s[j]∣==∣s[j]−s[i]∣是恒成立的。所以不必管前缀和数组的先后顺序，只要记录下前缀和数组中每个数原本的位置，再将这些数从小到大排序，这并不影响求解最终答案。排好序后的前缀和数组就可以尺取了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <bits/stdc++.h>
using namespace std;
pair<long long, long long> s[100005];
int main()
{
long long n, k, i, t, sum, resl, resr;
int l, r;
while (scanf("%lld%lld", &n, &k))
{
if (n == 0 && k == 0)
return 0;
for (i = 1; i <= n; i++)
{
scanf("%lld", &s[i].first);
s[i].second = i;
}
s[0].first = s[0].second = 0;
for (i = 1; i <= n; i++)
s[i].first = s[i - 1].first + s[i].first;
sort(s, s + 1 + n);
while (k--)
{
scanf("%lld", &t);
l = 0;
sum = 1e10;
for (r = 1; r <= n; r++)
{
if (llabs(llabs(s[r].first - s[l].first) - t) < llabs(sum - t))
{
sum = s[r].first - s[l].first;
resl = s[l].second;
resr = s[r].second;
if (sum == t)
break;
}
while (llabs(s[r].first - s[l].first) > t)
{
l++;
if (l == r)
break;
if (llabs(llabs(s[r].first - s[l].first) - t) < llabs(sum - t))
{
sum = s[r].first - s[l].first;
resl = s[l].second;
resr = s[r].second;
if (sum == t)
break;
}
}
if (sum == t)
break;
}
printf("%lld ", sum);
if (resl < resr)
printf("%lld %lld\n", resl + 1, resr);
else
printf("%lld %lld\n", resr + 1, resl);
}
}
}
|