# 4.1.1. 题目解析 

1. 要求某个区间内的数字两两相乘的总和
2. 想到前缀和，但是这题重点在于两两相乘
3. 先硬算，找找规律：

比如要算这串数字的两两相乘的积之和：

1, 2, 3

= 1*2 + 1*3 + 2*3

= 1*(2+3) + 2*3

前缀和数组：

1 3 6

发现没有什么关系。。。

数字再长些：

1, 2, 3, 4

= 1*2 + 1*3 + 1*4 + 2*3 + 2*4 + 3*4

= 1*(2+3+4) + 2*(3+4) + 3*4

= 1*9 + 2*7 + 3*4

前缀和数组：

1, 3, 6, 10

好像还是没关系。。。

换种思路：

1, 2, 3, 4

= 1*2 + 1*3 + 1*4 + 2*3 + 2*4 + 3*4

= 1*4 + 2*4 + 3*4 + 2*3 + 1*3 + 1*2

= 4*(1+2+3) + 3*(1+2) + 2*1（倒过来看）

=4*6 + 3*3 + 2*1

1, 3, 6 正好是前缀和数组中的数字。

所以，规律就是：

区间内两两相乘的乘积，等于当前这个数乘这个数前一个位置的前缀和。

---

回归本题，说的是让每段区间的“美味值”最大的一段尽可能小，也就是说让每段里美味值都尽可能小，而且分的段数还不能超过 m。

暴力：算出来本段苹果的最大美味值，然后依次递减判断是否满足段数要求，直至不能再减小。

优化：使用“二分”进行搜索可能的美味值。

4.1.2. 代码

import java.util.Scanner;public class Main {static Scanner in = new Scanner(System.in);public static void main(String[] args) {int n = in.nextInt(), m = in.nextInt();int N = n + 10;int[] a = new int[N];for (int i = 1; i <= n; i++) {a[i] = in.nextInt();}// 1. 二分出模拟美味值long l = 1, r = (long) 4e18;while (l < r) {long mid = (l + r) >> 1;if (check(a, mid, m)) {r = mid;} else {l = mid + 1;}}// l就是最小美味值System.out.println(l);}private static boolean check(int[] a, long mid, int m) {// 1. 判断能否分为m段// 2. 判断每一段的美味值是否超过midint N = a.length;long[] s = new long[N];long val = 0;// 美味值long cnt = 1;// 段数for (int i = 1; i < N; i++) {// 计算当前位置的美味值（单独一个苹果美味值为0，前缀和0位不用初始化为1）val += a[i] * s[i - 1];// 计算前缀和s[i] = s[i - 1] + a[i];// 判断美味值if (val > mid) {// 大于选好的美味值，分段，并将美味值清零cnt++;val = 0;s[i] = a[i];} else {// 不大于选好的美味值，继续计算}if (cnt > m) {return false;}}return true;}
}