※ 以下都是我自己著墨出來的,不保證正確
※ 以下 r+
指的是比 r
大的數
爬行法是一種利用 (解在數列上的)單調性 來進行枚舉區間時的優化,我們一般枚舉區間寫成:
for (int l = 0; l < N; l++):
for (int r = l; r < N; r++):
...
可以想成:
我們枚舉區間的左端點,當左端點固定在 l
時,將右端點從 l
開始向右移動(r++
)來找此時的最佳解。
(1)
如果區間 [l, r]
不是左端點為 l
時的最佳解,那因為單調性,我們只需向右移動右端點,直到找到此時的最佳解為止
(2)
如果已知 [l, r]
是左端點為 l
時的最佳解,那 [l, r+]
不可能是答案了,
(3)
所以我們就可以枚舉下一個左端點,左端點變成 l+1
。
(4)
此時會有兩種情況,
(4.1)
一種情況是 [l+1, r]
(尚)不是左端點為 l+1
時的最佳解,那這就回到 (1)
了
(4.2)
另一種情況是 [l+1, r]
已經是左端點為 l+1
時的最佳解,那這就回到 (2)
前提是 (1)
, (2)
,只要符合 (1)
, (2)
,應該都可以應用爬行法。
以 poj 3061 為例:
單調性是指 sum([l, r]) >= sum([l+1, r])
(1)
如果 sum([l, r]) < S
,因單調性,所以移動右端點,直到 sum >= S
(2)
如果 sum([l, r]) >= S
,根據題意,則 [l, r+]
不會是答案,因 ((r+) - l + 1) > (r - l + 1)
這題只能說太扯了…誰想得到啊
這題給的數列有正有負,要解這題得利用前綴和 + 排序 + 爬行法
struct P {
int sum;
int postion;
};
P prefix[i] = P(A[0] + A[1] + ... + A[i], i)
S[] = sort(P[])
於是,這題從找一個區間,區間和的絕對值越接近 T
越好,
變成在 前綴和由小排到大 的前綴和數列中,
找出兩項(S[i], S[j], i ≠ j
),他們差的絕對值越接近 T
越好,這可以用爬行法。
之後我們再看看 S[i], S[j]
是對應到原陣列中的哪個區間,P.position
就在記錄這個
至於爬行法的實作,這裡給出一種寫法,另一種跟書上類似的寫法可參這
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
int N, K;
int data[100000 + 1];
pii S[100000 + 1];
int T;
int ans_start = -1, ans_end = -1, ans_sum = 0;
void solve() {
int l = 0, r = 1;
int min_diff = INF, sum = 0;
while (r <= N) {
sum = abs(S[r].first - S[l].first);
// printf("%d(%d, %d)\n", sum, l, r);
// update
if (abs(sum - T) < min_diff) {
min_diff = abs(sum - T);
ans_sum = sum;
// 還原在原數列中對應的區間
ans_start = min(S[l].second, S[r].second) + 1;
ans_end = max(S[l].second, S[r].second);
}
// move
if (sum < T || l == r - 1) // 防止使用同一項(發生在範測 4)
r++;
else
l++;
}
}
int main() {
while (scanf("%d %d", &N, &K)) {
if (N == 0 && K == 0) break;
for (int i = 1; i <= N; i++)
scanf("%d", &data[i]);
S[0] = pii(0, 0); // 補零,方便之後區間的計算,觀察看看範測 4
for (int i = 1; i <= N; i++) {
S[i].first = S[i-1].first + data[i];
S[i].second = i;
}
sort(S, S + N + 1);
while (K--) {
scanf("%d", &T);
solve();
printf("%d %d %d\n", ans_sum, ans_start, ans_end);
}
}
return 0;
}