511
UVA之1121 - Subsequence
【題目】
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
Many test cases will be given. 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 there isn't such a subsequence, print 0 on a line by itself.
Sample Input
10 15 5 1 3 5 10 7 4 9 2 8 5 11 1 2 3 4 5
Sample Output
2 3
【分析】
本題最直接的思路是二重循環，枚舉子序列的起點和終點。代碼如下（輸入數據已存入數組A[1]~A[n]）。
int ans = n+1;
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++) {
int sum = 0;
for(int k = i; k <= j; k++) sum += A[k];
if(sum >= S) ans = min(ans, j-i+1);
}
printf("%d\n", ans == n+1 ? 0 : ans);
很可惜，上述程序的時間複雜度是O(n3)的，因此，當n達到100 000的規模後，程序將無能為力。有一個方法可以降低時間複雜度，即常見的前綴和技巧。令Bi=A1+A2+…+Ai，規定B0=0，則可以在O(1)時間內求出子序列的值：Ai+Ai+1+…+Aj=Bj-Bi-1。這樣，時間複雜度降為O(n2)，代碼如下。
B[0] = 0;
for(int i = 1; i <= n; i++) B[i] = B[i-1] + A[i];
int ans = n+1;
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
if(B[j] - B[i-1] >= S) ans = min(ans, j-i+1);
printf("%d\n", ans == n+1 ? 0 : ans);
遺憾的是，本題的數據規模太大，O(n2)時間複雜度的算法也太慢。不難發現，隻要同時枚舉起點和終點，時間複雜度不可能比O(n2)更低，所以必須另謀他路。比如，是否可以不枚舉終點，隻枚舉起點，或者不枚舉起點，隻枚舉終點呢？
我們首先試試隻枚舉終點。對於終點j，我們的目標是要找到一個讓Bj-Bi-1≥S，且i盡量大（i越大，序列長度j-i+1就越小）的i值，也就是找一個讓Bi-1≤Bj-S最大的i。考慮圖1-29所示的序列。
當j=5時，B5=12，因此目標是找一個Bi-1≤12-7=5的最大i。注意到B是遞增的（別忘了，本題中所有Ai均為整數），所以可以用二分查找。
【代碼】
/*********************************
* 日期：2014-5-14
* 作者：SJF0115
* 題號: 1121 - Subsequence
* 地址：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=246&page=show_problem&problem=3562
* 來源：UVA
* 結果：Accepted
**********************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
#define N 100001
int A[N];
int B[N];
//二分查找最接近target但不大於target
int BinarySerach(int target,int R){
int L = 0;
int mid = 0;
while(L < R){
mid = L + (R - L) / 2;
if(B[mid] > target){
R = mid;
}
else{
L = mid + 1;
}
}
return L;
}
int main(){
int n,s,i,j;
//freopen("C:\\Users\\wt\\Desktop\\acm.txt","r",stdin);
while(scanf("%d %d",&n,&s) != EOF){
int minLen = n+1;
B[0] = 0;
for(i = 1;i <= n;i++){
scanf("%d",&A[i]);
//序列前綴和
B[i] = B[i-1] + A[i];
}
for(j = 1;j <= n;j++){
int target = B[j] - s;
//二分查找
int index = BinarySerach(target,j-1);
if(index > 0){
minLen = min(minLen,j-index+1);
}
}
//沒有滿足條件的序列
if(minLen == n+1){
minLen = 0;
}
cout<<minLen<<endl;
}//while
return 0;
}
【相似題目】
最後更新：2017-04-03 12:56:39