【蓝桥杯备赛】深秋的苹果

# 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. 判断每一段的美味值是否超过mid
        int 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;
    }
}