快递网站推广怎么做,网站开发新手什么软件好,wordpress后台添加字段,外贸新手入门必读问题描述 小蓝有一个序列 a[1],a[2],…,a[n]。
给定一个正整数 k#xff0c;请问对于每一个 1 到 n 之间的序号 i#xff0c;a[i−k]#xff0c;a[i−k1]#xff0c;…#xff0c;a[ik] 这2k1 个数中的最小值是多少#xff1f;
当某个下标超过 1 到 n 的范围时#xf…问题描述 小蓝有一个序列 a[1],a[2],…,a[n]。
给定一个正整数 k请问对于每一个 1 到 n 之间的序号 ia[i−k]a[i−k1]…a[ik] 这2k1 个数中的最小值是多少
当某个下标超过 1 到 n 的范围时数不存在求最小值时只取存在的那些值。
输入格式 输入的第一行包含一整数 n。
第二行包含 n 个整数分别表示 a[1],a[2],…,a[n]。
第三行包含一个整数 k 。
输出格式 输出一行包含 n 个整数分别表示对于每个序号求得的最小值。
样例输入 5 5 2 7 4 3 样例输出 2 2 2 3 3 评测用例规模与约定 对于 30% 的评测用例1n10001a[i]1000。
对于 50% 的评测用例1n100001a[i]10000。
对于所有评测用例1n10000001a[i]1000000。
运行限制 语言 最大运行时间 最大运行内存 C 1s 256M C 1s 256M Java 3s 256M Python3 12s 512M PyPy3 12s 512M
语言最大运行时间最大运行内存C1s256MC1s256MJava3s256MPython312s512MPyPy312s512MGo12s512MJavaScript12s512M
一、ST表
参考文章数据结构之ST表 详解_二维st表-CSDN博客
import java.util.*;public class Main {public static void main(String[] args) {Scanner scan new Scanner(System.in);int n scan.nextInt();int len (int) (Math.log(n)/Math.log(2));int[][] st new int[n1][len1];for (int i 1; i n; i) {st[i][0] scan.nextInt();}for (int j 1; j len; j) {for (int i 1; i (1j) - 1 n; i) {st[i][j] Math.min(st[i][j-1], st[i(1j-1)][j-1]);}}int k scan.nextInt();for (int t 1; t n; t) {int start Math.max(1, t-k);int end Math.min(n, tk);int j (int) (Math.log(end-start1)/Math.log(2));System.out.print(Math.min(st[start][j], st[end-(1j)1][j]) );}}
}
二、线段树
参考文章超详解线段树(浅显易懂,几乎涵盖所有线段树类型讲解,匠心之作,图文并茂)-CSDN博客
import java.util.*;public class Main {static int[] tree,a;public static void main(String[] args) {Scanner scan new Scanner(System.in);int n scan.nextInt();tree new int[4*n1];a new int[n1];for (int i 1; i n; i) {a[i] scan.nextInt();}BuildTree(1, 1, n);int k scan.nextInt();for (int i 1; i n; i) {int x Math.max(i-k, 1);int y Math.min(ik, n);System.out.print(find(1, 1, n, x, y) );}}public static void BuildTree(int id,int l,int r) {if (l r) {tree[id] a[l];return;}int mid (lr)/2;BuildTree(id*2, l, mid);BuildTree(id*21, mid1, r);tree[id] Math.min(tree[id*2], tree[id*21]);}public static int find(int id,int l,int r,int x,int y) {if (x l y r) {return tree[id];}int mid (lr)/2;int res Integer.MAX_VALUE;if (x mid) {res Math.min(res, find(id*2, l, mid, x, y));}if (y mid) {res Math.min(res, find(id*21, mid1, r, x, y));}return res;}
}
三、单调队列
参考文章单调队列的学习 - 滑动窗口求最大/小值 (Leetcode 239, Sliding Window Maximum)_滑动窗口最小值-CSDN博客
import java.util.*;public class Main {public static void main(String[] args) {Scanner scan new Scanner(System.in);int n scan.nextInt();int[] min new int[n1];int[] a new int[n1];for (int i 1; i n; i) {a[i] scan.nextInt();}int k scan.nextInt();LinkedListInteger list new LinkedListInteger();for (int i 1; i k1; i) {while (!list.isEmpty() i n a[list.peekLast()] a[i]) {list.pollLast();}list.addLast(i);}min[1] a[list.peekFirst()];for (int i 2; i n; i) {if (!list.isEmpty() i-k 0 list.peekFirst() i-k) {list.pollFirst();}while (!list.isEmpty() ik n a[list.peekLast()] a[ik]) {list.pollLast();}if (ik n) {list.addLast(ik);}min[i] a[list.peekFirst()];}for (int i 1; i n; i) {System.out.print(min[i] );}}
}
