【滑动窗口】美丽的区间【蓝桥杯】

题目

美丽的区间 - 蓝桥云课

---

问题描述

给定一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$ 和一个常数 $S$。

对于一个连续区间如果它的区间和大于或等于 $S$，则称它为美丽的区间。

对于一个美丽的区间，如果其区间长度越短，它就越美丽。

请你从序列中找出最美丽的区间。

输入格式

第一行包含两个整数 $n, S$，其含义如题所述。

接下来一行包含 $n$ 个整数，分别表示 $a_1, a_2, \dots, a_n$。

$10 \le N \le 10^5$ , $1 \le a_i \le 10^4$ , $1 \le S \le 10^8$。

输出格式

输出共一行，包含一个整数，表示最美丽的区间的长度。

若不存在任何美丽的区间，则输出 $0$。

样例输入

5 6
1 2 3 4 5

样例输出

2

运行限制

• 最大运行时间：1s
• 最大运行内存：128M

解题

方法一：贪心 暴力

思路

模板题，滑动窗口直接做。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int s = (int) in.nval;
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            a[i] = (int) in.nval;
        }
        int l = 0, r = 0, sum = 0, mn = Integer.MAX_VALUE;
        while (r < n) {
            sum += a[r++];
            while (sum >= s) {
                mn = Math.min(mn, r - l);
                sum -= a[l++];
            }
        }
        System.out.println(mn > n ? 0 : mn);
    }
}