POJ 3061 Subsequence ( 二分 || 尺取法 )
2024-09-18 07:42:12
题意 : 找出给定序列长度最小的子序列,子序列的和要求满足大于或者等于 S,如果存在则输出最小长度、否则输出 0(序列的元素都是大于 0 小于10000)
分析 : 有关子序列和的问题,都可以考虑采用先构造前缀和的方式来进行接下来的操作 ( 任意子序列的和都能由某两个前缀和的差表示 )。
二分做法 ==> 我们枚举起点,对于每一个起点 St 二分查找看看 St 后面有没有前缀和是大于或者等于 [ St的前缀和 ] + S 的,如果有说明从当前起点开始有一个终点使得起终之和是大于或者等于 S 的,在这个过程中维护最小长度即可!时间复杂度为 O(nlogn)
#include<bits/stdc++.h> using namespace std; ; int arr[maxn], sum[maxn]; int main(void) { int nCase; scanf("%d", &nCase); sum[] = ; while(nCase--){ int n, s; scanf("%d %d", &n, &s); ; i<=n; i++){ scanf("%d", &arr[i]); sum[i] = sum[i-] + arr[i]; } if(sum[n] < s){ puts("); continue; } int ans = n; ; i<=n; i++){ ; int en = lower_bound(sum+st, sum+n, sum[st]+s) - sum; //printf("%d %d\n", st, en); if(sum[en] - sum[st] < s) continue; ans = min(ans, en - st); } printf("%d\n", ans); } ; }
尺取做法 ==> 如果有一个满足条件的子序列为 arr[st]...arr[en-1] >= S,那么肯定有 arr[st+1]...arr[en-2] < arr[st]...arr[en-2] < S,所以如果将 st+1 作为起点也有满足条件的序列且令其终点为en'-1,那么必定有 en'-1 >= en-1,那么也就是说当前枚举完 st 这个点,其贡献的答案是 (en-1)-st+1,现在我们考虑 st+1 即下一个起点的时候考虑的终点应该是要考虑大于或者等于 en-1 的点,故尺取是正确的解法。时间复杂度为O(n)
///尺取法 #include<bits/stdc++.h> using namespace std; ; int sum[maxn]; int main(void) { sum[] = ; int nCase; scanf("%d", &nCase); while(nCase--){ int n, s; scanf("%d %d", &n, &s); int tmp; ; i<=n; i++) scanf("%d", &tmp), sum[i] = sum[i-] + tmp;///统计前缀和 if(sum[n] < s){ puts("); continue; } int L, R, ans;///左指针、右指针 ans = n; L = R = ; while(L <= R && R <= n){ if(sum[R] - sum[L] < s) R++; else{ ans = min(ans, R-L); L++; } } printf("%d\n", ans); } ; }
最新文章
- 关于li元素嵌套的事儿
- 从 HTTP 到 HTTPS - IIS 部署免费 HTTPS
- java泛型编译时被擦除引起多态的破坏,用 桥方法解决此类问题。(java 桥方法)
- 【CodeForces 651B】Beautiful Paintings 排序+贪心
- python学习(三):matplotlib学习
- c#或获取系统的特殊路径,如我的文档等
- jz2440开发板设置备份
- Gauss elimination Template
- 怎样使用yum安装OpenStack
- Python_字符串的大小写变换
- leetcode — binary-tree-inorder-traversal
- maven仓库配置阿里云镜像
- mapreduce的cleanUp和setUp的特殊用法(TopN问题)和常规用法
- 使用libcurl下载https地址的文件
- logback.xml常用配置详解
- [java]经验集
- 实现在vista和win7中使用管理员权限接收WM_DROPFILES(OnDropFiles())消息的方法(好像XP不支持这个函数)
- iOS开发解决 jsonModel 属性跟系统的重复
- JQuery 操作 checkbox 二次赋值无效 attr ---->; prop
- 洛谷 P3765 总统选举 解题报告