倍增法和二分法是“相反”的算法。二分是每次缩小一倍,从而以 O(logn)的步骤极快地缩小定位到解;倍增是每次扩大一倍,从而以 O(2^n)的速度极快地扩展到极大的空间。所以倍增和二分的效率都很高。
1. 把数列按倍增分成小区间
对数列的每个元素,把从它开始的数列分成长度为1、2、4、8、…的小区间。
示例 1
输入
5 5 1 2 3 4 5 1 1 1 2 1 3 3 4 2 5
输出
1 2 3 4 5
import java.util.Scanner; public class Main { private static int N = 0; private static int Q; private static int[] a = new int[500005]; private static int[][] dp = new int[1000][50];//随便设的大小 public static void init() { for (int i = 1; i <= N; i++) { dp[i][0] = a[i];//小区间长度为1,最小值即为本身 } double p = Math.log(N) / Math.log(2);//java里只能这么求对数 还必须用double来接? for (int i = 1; i <= (int) p; i++) { for (int j = 1; j + Math.pow(2, i) <= N + 1; j++) { dp[j][i] = Math.max(dp[j][i - 1], dp[j + (int) Math.pow(2, i - 1)][i - 1]); } } } public static int fun_1(int L, int R) { double ans = Math.log(R - L + 1) / Math.log(2); return Math.max(dp[L][(int) ans], dp[R - (int) Math.pow(2, (int) ans) + 1][(int) ans]); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); N = scanner.nextInt(); Q = scanner.nextInt(); for (int i = 1; i <= N; i++) { a[i] = scanner.nextInt(); } init();//初始化dp数组 int L, R; for (int i = 1; i <= Q; i++) { L = scanner.nextInt(); R = scanner.nextInt(); System.out.println(fun_1(L, R)); } } }
和第一题差不多 min改为max
样例输入
5 3 5 3 2 4 1
样例输出
2 2 1
import java.util.Scanner; public class Main { private static int N = 0; private static int M; private static int[] a = new int[500005]; private static int[][] dp = new int[1000][50];//随便设的大小 public static void init() { for (int i = 1; i <= N; i++) { dp[i][0] = a[i];//小区间长度为1,最小值即为本身 } double p = Math.log(N) / Math.log(2);//java里只能这么求对数 还必须用double来接? for (int i = 1; i <= (int) p; i++) { for (int j = 1; j + Math.pow(2, i) <= N + 1; j++) { dp[j][i] = Math.min(dp[j][i - 1], dp[j + (int) Math.pow(2, i - 1)][i - 1]); } } } public static int fun_1(int L, int R) { double ans = Math.log(R - L + 1) / Math.log(2); return Math.min(dp[L][(int) ans], dp[R - (int) Math.pow(2, (int) ans) + 1][(int) ans]); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); N = scanner.nextInt(); M = scanner.nextInt(); for (int i = 1; i <= N; i++) { a[i] = scanner.nextInt(); } init();//初始化dp数组 for (int i = 1; i <= N-M+1; i++) { System.out.println(fun_1(i,i+M-1)); } return; } }
真恶心啊