今日练习

今日练习

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;

}