尺取法及例题

题目:

Description

A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.

Input

The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.
Output

For each the case the program has to print the result on separate line of the output file.if no answer, print 0.

Sample Input

2

10 15

5 1 3 5 10 7 4 9 2 8

5 11

1 2 3 4 5

Sample Output

2

3

这道题我纠结了三天,才发现是读错题了…

原题是要求求连续子序列的和的长度,我自己加了一个需要序列元素也要排序的条件..然后题解怎么都没法看懂…

思路:

1.暴力: O2直接找大于s的区间距离取最小

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
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int arr[100005];

int main(int argc, const char * argv[]) {

int k,n,s;
cin >> k;
while (k--) {
cin >> n >> s;
memset(arr, 0, sizeof(arr));
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
int minl = 0;
int lcs = n;
for (int i = 1; i <= n; i++) {
int sum = 0;
int j;
for (j = i; sum < s; j++) {
sum += arr[j];
}

if ((j - i) < lcs) {
lcs = j - i;
minl = j - i;
}
}
cout << endl << minl << endl;
}
return 0;
}

2.二分法: 前缀和求出对应区间的和.然后在[0,n)内搜索满足子序列和 > s的区间的最小值

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
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int arr[100005];

int main(int argc, const char * argv[]) {

int k,n,s;
cin >> k;
while (k--) {
cin >> n >> s;
memset(arr, 0, sizeof(arr));

for (int i = 0; i < n; i++) {
cin >> arr[i];
}
for (int i = 0; i < n; i++) {
arr[i + 1] += arr[i];
}
long res = n;

for (int i = 0; arr[i] + s <= arr[n]; i++) {
long temp = lower_bound(arr + i, arr + n, arr[i] + s) - arr;
res = min(res,temp - i);
}
cout << res << endl;
}


return 0;
}

3.尺取法

《挑战程序设计》上的一个思路

思路: 假设以l开始总和最初大于S的连续子序列为[l,t-1),那么可以得出sum[l+1,t-2] < sum[l,t-2]<S

也就是如果从l + 1到t`-1的话

必然有l < l`

算法也就是

(1) 初始化l = t = sum = 0;

(2) 只要满足sum < s 就不断给sum加下一个arr,并t++

(3) 如果(2)无法满足sum>=s则终止. 否则更新 res = min(res,t-l)

(4) sum-第l个元素,l+1,然后重复执行(2)

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
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int arr[100005];

int main(int argc, const char * argv[]) {

int k,n,s;
cin >> k;
while (k--) {
cin >> n >> s;
memset(arr, 0, sizeof(arr));
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int res = n + 1,t = 0,sum = 0,l = 0;
for (;;) {
while (t < n && sum < s) {
sum += arr[t++];
}
if (sum < s) break;
res = min(res,t - l);
sum -= arr[l++];
}
if (res > n) {
res = 0;
}
cout << res << endl;

}
return 0;
}
script>