侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 667 篇文章
  • 累计创建 127 个标签
  • 累计收到 15 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-02-05 / 0 评论 / 0 点赞 / 165 阅读 / 434 字
温馨提示:
本文最后更新于 2023-02-05,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

美丽的区间 - 蓝桥云课


问题描述

给定一个长度为 nn 的序列 a1,a2,,ana_1, a_2, \dots, a_n 和一个常数 SS

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

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

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

输入格式

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

接下来一行包含 nn 个整数,分别表示 a1,a2,,ana_1, a_2, \dots, a_n

10N10510 \le N \le 10^5 , 1ai1041 \le a_i \le 10^4 , 1S1081 \le S \le 10^8

输出格式

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

若不存在任何美丽的区间,则输出 00

样例输入

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);
    }
}
0

评论区