今日练习
UVA 1398 太难,跳过!;
Floyd 判圈算法,待学习;
POJ 3061;
LA 3029;
POJ 3061
//
// Created by 21122 on 2022/6/2/0002.
//
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int S;
const int MAXN = 100005;
int arr[MAXN];
int A[MAXN];
int main()
{
while(cin >> n)
{ // 结束标志为 EOF
cin >> S;
for(int i = 1; i <= n; i++)
{ // 从1开始存储
cin >> arr[i];
}
// 方法1
// 若使用二分法,考虑到原数据并非有序,则可存储数组A[i],其中 第 i 个元素表示 arr[1] + arr[2] + ... + arr[i];
// 使用二分法来寻找差值为 S ;
// i - j,利用循环固定i, 利用二分查找搜索j ,使得满足A[j] - A[i] >= S的同时,j 和 i 的差值尽可能小,即
// res = min(res, j - i) when 条件满足时;
// 代码略!
// 方法2
// 由于A[i] 递增,故 A[i] - S 也递增。换句话说,满足条件的位置 i 也是递增的;
//
// for(int i = 1; i <= n; i++)
// {
// A[i] = A[i - 1] + arr[i];
// }
//
// int i = 1;
// int res = n;
//
// for(int j = 1; j <= n; j++)
// {
// if(A[j] - S < A[i])
// { // 不满足,跳过;
// continue;
// }
// //else;
// while(A[j] - S >= A[i])
// { // i加一,直至不满足的临界条件
// i ++;
// }
//
// res = min(res, j - (i - 1));
// }
// 方法3, 左右同时逼近,右边下标扩大数据,左边下标缩小数据;
// 类似于二分法,具体效率可能偏差,但更容易想到
int sum = 0;
int left = 1;
int right = 1;
int res = n;
while(true)
{
while(sum < S && right <= n)
{
sum += arr[right ++];
}
if(sum < S)
{
break;
}
res = min(res, right - left);
sum -= arr[left ++];
}
}
return 0;
}