一、题目
题目描述
读入n,xn,xn,x,给出nnn个数a[1],a[2],……,a[n]a[1],a[2],……,a[n]a[1],a[2],……,a[n],求最小的区间[l,r][l,r][l,r],使a[l]+a[l+1]+……+a[r]≥xa[l]+a[l+1]+……+a[r]≥xa[l]+a[l+1]+……+a[r]≥x,若存在相同长度区间,输出lll最小的那个
输入描述:
第一行两个数,n(1≤n≤10000000),x(1≤x≤10000) 第二行n个数a[i](1≤a[i]≤1000)
输出描述:
输出符合条件l,r(保证有解)
示例1
输入
10 20 1 1 6 10 9 3 3 5 3 7
输出
3 5
二、思路解析
这道题是求连续区间的,看到的第一眼,就都要想起 “滑动窗口” 这一算法。
我们可以使用双指针技巧来解决这个问题。具体步骤如下:
- 初始化两个指针 left 和 right,初始位置都为数组的起始位置。
- 维护一个变量 sum,表示当前区间内子数组的和。
- 不断移动 right 指针,将元素加入当前区间,并更新 sum。
- 当 sum 大于等于 x 时,移动 left 指针,缩小区间范围,并更新 sum,直到区间不再满足 sum 大于等于 x 的条件。
- 在每次移动 left 和 right 指针时,记录满足条件的区间的最小长度和对应的左右边界。
- 最终得到的就是满足条件的最小区间。
并且,要注意的一点就是,这道题的数据量会比较大,且传统的 Scanner 读取会耗费比较大的时间,所以我们需要通过重写 IO 流,来提高我们的输入输出效率。
模版我也放在这啦👇
import java.util.*;
import java.io.*;public class Main
{public static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in = new Read();public static void main(String[] args) throws IOException{// 写代码out.close();}
}class Read // 自定义快速读入
{StringTokenizer st = new StringTokenizer("");BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));String next() throws IOException {while(!st.hasMoreTokens()){st = new StringTokenizer(bf.readLine());}return st.nextToken();}String nextLine() throws IOException {return bf.readLine();}int nextInt() throws IOException {return Integer.parseInt(next());}long nextLong() throws IOException {return Long.parseLong(next());}double nextDouble() throws IOException {return Double.parseDouble(next());}
}
三、完整代码
import java.util.*;
import java.io.*;public class Main{public static void main(String[] args) throws IOException{Read in = new Read();int n = in.nextInt();int x = in.nextInt();int[] nums = new int[n + 1];for(int i = 1; i <= n; i++){nums[i] = in.nextInt();}int left = 1, right = 1;int sum = 0;int retleft = -1, retright = -1, retLen = n;while(right <= n){sum += nums[right];while(sum >= x){if(right - left + 1 < retLen){retleft = left;retright = right;retLen = right - left + 1;} sum -= nums[left++];}right++;}System.out.println(retleft + " " + retright);}}class Read{StringTokenizer st = new StringTokenizer("");BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));String next() throws IOException{while(!st.hasMoreTokens()){st = new StringTokenizer(bf.readLine());}return st.nextToken();}String nextLine() throws IOException{return bf.readLine();}int nextInt() throws IOException{return Integer.parseInt(next());}long nextLong() throws IOException{return Long.parseLong(next());}double nextDouble() throws IOException{return Double.parseDouble(next());}
}
以上就是本篇博客的全部内容啦,如有不足之处,还请各位指出,期待能和各位一起进步!