首页 > 代码库 > POJ-3061
POJ-3061
算法：
1. 定义两个整数N和S，输入序列长度到N，输入最小子序列和下界到S。
2. 定义一个数组arr[100002]，从arr[1]开始依次输入N个序列元素到arr。
3. 定义一个整数ans，初始化ans=100002。
4. 执行下列尺取法步骤：
1. 定义两个整数l和r，初始化l=1，r=2。
2. 定义一个整数sum，初始化sum=arr[1]。
3. 当不满足条件：r==N+1并且sum<S时，执行下列步骤，否则结束：
1. 若sum<S，则令r=r+1，sum=sum+arr[r-1]。回到1.3。
2. 若sum>=S，则令l=l+1，sum=sum-arr[l-1]。回到1.3。
4. 若ans==100002，说明没有符合条件的最小子序列，置ans=0，否则ans就是最小子序列长度。
5. 输出ans。
代码：
#include <iostream>using namespace std;int arr[100002];int main(){ int time; cin >> time; while (time--) { int N, S; cin >> N >> S; for (int i = 1; i <= N; ++i) { cin >> arr[i]; } int ans = 100002; { // Algorithm: Ruler Method int l = 1, r = 2; int sum = arr[1]; while (!(r == N + 1 && sum < S)) { if (sum < S) { ++r; sum += arr[r - 1]; } else { ans = ans>r - l ? r - l : ans; ++l; sum -= arr[l - 1]; } } if (ans == 100002) { cout << 0 << endl; } else { cout << ans << endl; } } } return 0;}
POJ-3061
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。