首页 > 代码库 > LA 2678 Subsequence

LA 2678 Subsequence

2024-07-15 12:04:24   225人阅读

有一个正整数序列，求最短的子序列使得其和大于等于S，并输出最短的长度。

用数组b[i]存放序列的前i项和，所以b[i]是递增的。

遍历终点j，然后在区间[0, j)里二分查找满足b[j]-b[i]≥S的最大的i，时间复杂度为O(nlongn)。

这里二分查找用到库函数lower_bound()

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 const int maxn = 100000 + 10; 9 int a[maxn], b[maxn];10 11 int main(void)12 {13     #ifdef LOCAL14         freopen("2678in.txt", "r", stdin);15     #endif16 17     int n, S;18     while(scanf("%d%d", &n, &S) == 2)19     {20         for(int i = 1; i <= n; ++i)21         {22             scanf("%d", &a[i]);23             b[i] = b[i-1] + a[i];24         }25         int ans = n + 1;26         for(int j = 1; j <= n; ++j)27         {28             int i = lower_bound(b, b+j, b[j]-S) - b;29             if(i > 0)30                 ans = min(ans, j-i+1);31         }32         printf("%d\n", ans == n+1 ? 0 : ans);33     }34     return 0;35 }
代码君一

 

继续优化：

由于j是递增的，bj也是递增的，所以bi-1≤bj-S的右边也是递增的。换句话说满足条件的i的位置也是递增的。

虽然有两层循环，但是i的值只增不减，所以时间复杂度为O(n)

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 const int maxn = 100000 + 10; 9 int a[maxn], b[maxn];10 11 int main(void)12 {13     #ifdef LOCAL14         freopen("2678in.txt", "r", stdin);15     #endif16 17     int n, S;18     while(scanf("%d%d", &n, &S) == 2)19     {20         for(int i = 1; i <= n; ++i)21         {22             scanf("%d", &a[i]);23             b[i] = b[i-1] + a[i];24         }25         int ans = n + 1;26         int i = 1;27         for(int j = 1; j <= n; ++j)28         {29             if(b[i-1] > b[j] - S)30                 continue;31             while(b[i] <= b[j] - S)32                 ++i;33             ans = min(ans, j-i+1);34         }35         printf("%d\n", ans == n+1 ? 0 : ans);36     }37     return 0;38 }
代码君二

 


联系
我们