反复推进区间的开头与末尾,这样的方法叫做尺取法,求给定长度内的最短区间可以满足某些性质。
POJ3061
题意:
给定长度为 n 的数列整数,以及整数 S ,求出总和不小于 S 的连续子序列的长度的最小值.如果解不存在则输出 0 。
解:
不断的推进首位,每推进一次首位,就往后推近末尾直到区间序列的和大于等于S。
1 int N, S; 2 int a[MAXN]; 3 4 void solve() { 5 int res = N + 1; 6 int s = 1, t = 1, sum = 0; 7 for (;;) { 8 while (t <= N && sum < S) { 9 sum += a[t++]; 10 } 11 if (sum < S) break; 12 res = min(t - s, res); 13 sum -= a[s++]; 14 } 15 if (res > N) res = 0; 16 printf("%d\n", res); 17 } 18 19 int main() { 20 #ifndef ONLINE_JUDGE 21 freopen("input.txt", "r", stdin); 22 #endif 23 int T = READ(); 24 while (T--) { 25 CLR(a); 26 scanf("%d %d", &N, &S); 27 REP(i, 1, N) scanf("%d", &a[i]); 28 solve(); 29 } 30 return 0; 31 }
POJ3320
题意:
一本书总共有 P 页,第 i 页有一个知识点 $a_i$ (每个知识点都有一个编号),求最少读连续的多少页就可以掌握所有知识点
解法:
尺取法,用一个单独的变量维护当前读过的区间内的知识数,判断其与知识总数是否相等,若相等则更新答案,否则继续推。
1 int P; 2 int a[MAXN]; 3 set<int> all; 4 5 void solve() { 6 int num = all.size(); 7 int s = 1, t = 1, sum = 0; 8 int res = P; 9 map<int, int> count; 10 for (;;) { 11 while (t <= P && sum < num) { 12 if (count[a[t++]]++ == 0) sum++; 13 } 14 if (sum < num) break; 15 res = min(t - s, res); 16 if (--count[a[s++]] == 0) sum--; 17 } 18 printf("%d\n", res); 19 return; 20 } 21 22 int main() { 23 #ifndef ONLINE_JUDGE 24 freopen("input.txt", "r", stdin); 25 #endif 26 scanf("%d", &P); 27 for (int i = 1; i <= P; i++) { 28 scanf("%d", &a[i]); 29 all.insert(a[i]); 30 } 31 solve(); 32 return 0; 33 }