蓝桥杯深秋的苹果

题目

当深秋的苹果树丰收时，村庄的居民们兴致勃勃地采摘着红彤彤的苹果。他们将采摘下来的 NN 个苹果排成了一排，形成了一个苹果序列 AA，第 ii 个苹果的甜度值为 AiAi​（1≤i≤N1≤i≤N）。

现在村民需要将苹果序列划分为连续的 MM 段，对于分割后的某一段 Al∼rAl∼r​，定义其美味值表示为该段内不同下标的苹果的甜度两两相乘的总和，即 ∑i=lr∑j=i+1rAi⋅Aj∑i=lr​∑j=i+1r​Ai​⋅Aj​。

注：如果某一段只有一个苹果，它的美味值为 00。

请问应当如何给苹果分段，才能使得美味值最大的一段尽可能小，你只需要输出这个最大美味值可能的最小值即可。

输入格式

第 11 行输入 22 个正整数 N,MN,M，分别为苹果序列的长度和需要分成的段数。

第 22 行输入 NN 个空格隔开的正整数，表示苹果序列。

输出格式

输出仅 11 行，包含 11 个整数，表示答案。

样例输入

6 3
1 4 7 2 5 8

样例输出

39

说明

我们可以把苹果序列分成 [1,4,7],[2,5],[8][1,4,7],[2,5],[8]，这样最大的一段美味值为 3939，是最小的分法。

评测数据规模

1≤M≤N≤2000001≤M≤N≤200000。

1≤Ai≤100001≤Ai​≤10000。

解题思路

哦，这个问题看起来有点挑战性。我得仔细看看题目要求。题目是说，把N个苹果分成M段，每一段的美味值是该段内所有两两不同下标苹果的甜度乘积之和。然后，我们需要让所有段中的最大美味值尽可能的小，求这个最小的最大值。对吧？

那首先，我得想，怎么计算一段的美味值。比如，假设有一个段是l到r，那么这段的美味值是sum_{i=l到r} sum_{j=i+1到r} A[i]*A[j]。那这个怎么快速计算呢？因为直接两重循环的话，当数据量大的时候可能会超时。

我记得有一个数学公式可以将这个总和转化为更高效的计算方式。比如，假设总和的平方减去各元素的平方之和，然后除以2。或者说，这个总和等于（sum A[i]）^2 - sum A[i]^2，然后除以2？因为，总和的平方等于每对两个元素的乘积的和加上各个元素的平方之和。所以，每对相乘的总和等于（sum^2 - sum各平方） / 2。这样对吗？例如，假设有a、b、c三个数，总和的平方是a² + b² + c² + 2ab + 2ac + 2bc。所以，所有两两的乘积的和是ab+ac+bc等于（sum² - sum各平方） / 2。对的。这样的话，计算一段的美味值就可以用O(1)的时间了，前提是知道这段的总和和平方和。

那这样的话，每个段的美味值可以用（sum^2 - sum_sq） / 2来计算。这样确实高效。那我们需要预处理前缀和数组以及前缀平方和数组。比如，prefix_sum[i]是前i个元素的和，prefix_sq_sum[i]是前i个元素的平方和。那么，对于区间[l, r]，sum是prefix_sum[r] - prefix_sum[l-1]，sum_sq是prefix_sq_sum[r] - prefix_sq_sum[l-1]。然后美味值就是（sum² - sum_sq)/2。

好的，这样计算每段的美味值的问题解决了。那现在的问题转化为，如何将数组分成M段，使得最大的段的美味值尽可能小。这显然是一个二分答案的问题。我们需要找到一个最小的可能的最大值，使得存在一种分法，分成的各段的美味值都不超过这个值，而且段的数量不超过M。

那二分的思路是，假设当前的中值是mid，我们需要判断是否可以将其分成不超过M段，每段的美味值都不超过mid。如果可以的话，说明我们可以尝试更小的mid；否则，需要更大的mid。

那么，如何实现这个判断函数呢？也就是check(mid)函数。这个函数的逻辑是，尽可能多地分割数组，使得每一段的美味值不超过mid。如果分割后的段数k <= M，那么返回true，否则返回false。

比如，初始的时候，假设mid足够大，那么只需要分成1段，所以返回true。如果mid很小，可能需要分成很多段，超过M，则返回false。

那具体的分割方法是什么呢？我们可以用贪心的策略：遍历数组，尽可能地将当前段延长，直到加上下一个元素后，该段的美味值超过mid。此时，必须在此处分割，然后开始新的段。这样分割出来的段数是最小的可能，因为每次尽可能多地合并元素。如果这样得到的段数k <= M，那么说明mid是可行的。

这样，问题就转化为了如何高效地判断在给定mid的情况下，分割后的段数是否不超过M。因此，整个算法的步骤应该是：

1. 预处理前缀和和前缀平方和数组。

2. 二分查找可能的mid值，范围是0到最大值可能的情况。比如，当所有元素都在同一段时，最大值是总美味值，所以初始右边界可以设为这个值。

3. 对于每个mid，用贪心法分割数组，计算需要的段数。如果段数<=M，则可能可以更小，否则需要增大mid。

4. 最后找到最小的可行mid。

那现在，如何高效地计算在给定段的情况下，分割点的位置呢？例如，假设当前段的起点是left，那么需要找到最大的right，使得left到right这一段的美味值<=mid。如何快速找到这个right？

直接的做法是从left开始，逐步扩展right，直到超过mid。这样最坏情况下是O(n)的时间复杂度，每个二分步骤需要O(n)时间，总的时间复杂度是O(n log S)，其中S是可能的mid的范围。对于n=1e5的数据来说，这样的时间复杂度可能可以接受，但要看具体情况。比如，如果n是1e5，log S是30的话，总共有3e6次操作，可能可以过。

那假设n是1e5的话，这样的方法是可行的。所以这可能是一个可行的解法。

现在，具体的实现步骤：

首先，预处理prefix_sum和prefix_sq_sum数组。

然后，二分查找：

初始化左边界left=0，右边界right=总美味值。总美味值可以通过计算整个数组的（sum^2 - sum_sq） / 2得到。或者，当整个数组作为一段时的美味值。

然后，每次取mid=(left+right)/2，然后判断是否可以在分割成k段，k<=M的情况下，每段的美味值<=mid。如果可以的话，尝试缩小右边界；否则，左边界增加到mid+1。

不过，这里可能需要注意二分的上下界。比如，当所有元素都为0时，总美味值为0，所以mid可能为0。或者，当每个元素都是1时，总美味值是组合数。

然后，如何计算分割的段数？

比如，初始化段数为1，当前段的起始位置是start=0。然后从第一个元素开始遍历，逐步计算当前段是否能包含下一个元素。或者更准确地说，每次确定当前段的结束位置。

或者，可以这样处理：初始start=1（假设数组是1-based的），然后遍历到i的位置，计算[start, i]这段的美味值。如果超过mid，则必须在i-1的位置分割，段数加1，然后start=i作为新的段的起点。

这个过程需要O(n)的时间，每个i都要检查一次。

现在，代码的大致结构：

预处理prefix_sum和prefix_sq_sum数组。

然后，二分循环：

while left < right:

mid = (left + right) >> 1

if check(mid) <= M:

right = mid

else:

left = mid +1

最后输出left。

而check函数的逻辑是，计算在最大允许mid的情况下，最少需要分割成多少段。如果这个数目<=M，则返回True，否则返回False。

那么，在check函数中：

初始化count=1，current_start=1（数组的起始位置），然后从current_start开始，寻找最大的end，使得current_start到end这段的美味值<=mid。如果无法找到，则必须分割。或者，另一种方法是逐个元素扩展，直到超过mid，然后分割。

例如，初始sum和sum_sq是current_start到current_end的。然后每次尝试将current_end+1加入，计算新的总和和sum_sq，然后计算美味值。如果不超过mid，则继续；否则必须分割。

或者，更高效的方式是，每次处理到i的位置，维护当前段的start到i-1的位置，尝试将i加入当前段，计算从start到i的美味值。如果超过mid，则分割，start=i，段数加1。否则，继续。

这样，遍历整个数组：

初始化start=1，count=1.

sum_total = prefix_sum[i] - prefix_sum[start-1]

sum_sq_total = prefix_sq[i] - prefix_sq[start-1]

value = (sum_total * sum_total - sum_sq_total) / 2.

如果value > mid，那么必须分割，start = i，count +=1.

否则，可以继续。

那具体来说，代码中的check函数应该怎么写呢？

比如，在遍历数组的时候，我们需要逐个元素处理。假设当前段的起始位置是last，然后对于当前i，我们计算从last到i这段的美味值。如果这个值超过mid，那么必须分割，将last设为i，段数加1。否则，继续。

所以，在循环中，从i=1到n：

sum = prefix_sum[i] - prefix_sum[last-1]

sum_sq = prefix_sq[i] - prefix_sq[last-1]

value = (sum * sum - sum_sq) / 2

如果value > mid，则无法将i加入当前段，必须分割。所以段数加1，last=i，并且当前段的sum和sum_sq就是a[i]的值。但需要注意，当分割时，i必须作为新段的起始点。例如，假设当前段是last到i-1，然后分割，那么新段的起始点是i。然后，i继续前进到i+1吗？

或者，可能我应该从i=2开始遍历？

比如，初始时last=1，段数为1。然后从i=2到n：

尝试将i加入当前段（last到i），计算这段的美味值。如果超过mid，则分割，段数加1，last设为i。

否则，继续。

这样，遍历整个数组，得到段数。如果段数<=M，则mid可行。

例如，初始last=1，段数是1。i从2到n：

计算last到i的美味值。如果超过mid，说明必须分割到i-1。然后last设为i，段数加1。否则，继续。

例如，当i=2时，last=1，计算1-2的总和和sum_sq，得到美味值。如果超过mid，则分割，段数变为2，last=2。否则，继续到i=3。

这样，遍历之后，得到的段数就是所需的最少段数吗？或者是否是尽可能多的分割？

这里可能需要注意，这样的贪心策略是否正确。例如，是否有时候分割得更早，可以得到更优的段数。例如，假设当前i到某个位置可能超过mid，但如果在中间分割的话，可能得到更少的段数。但是，贪心策略是尽可能延长当前段，这样分割的次数最少，所以得到的段数可能最少。因此，如果这样得到的段数<=M，则说明存在一种分割方式使得段数<=M，并且每段都不超过mid。因此，这样的贪心是正确的。

所以，这个贪心方法是对的。

现在，关于代码的具体实现：

在Java中，需要处理的是：

prefix_sum数组和prefix_sq数组。例如，prefix_sum[0] = 0，prefix_sum[1] = a[1], prefix_sum[2] = a[1]+a[2], etc.

然后，在check函数中，遍历i从1到n，或者从2到n？或者，可能更正确的方式是，初始段的起始位置是start=0（假设数组是0-based的），然后每次尝试将当前元素加入段中。

或者，原题中的数组可能被定义为1-based。比如，在给出的代码示例中，a数组的长度是n+10，循环从i=1到n。所以，假设原数组是1-based的。

那么，在遍历时，初始段的起点是last=1。然后，从i=2开始到n：

计算从last到i的总和和平方和，得到美味值。如果超过mid，则必须分割。此时，将段数加1，last设为i，然后继续处理i+1。

否则，继续处理i+1。

这样，遍历结束后，段数可能<=M，这时候返回true。

现在，举个例子：

比如，数组是1,2,3，分成2段。

总共有三个元素。初始last=1，段数=1.

i=2，计算1-2段的总和是3，平方和是1+4=5。美味值是 (3²-5)/2 = (9-5)/2=2，假设mid=2。此时，如果mid是2，那么当前段允许，所以继续。

i=3，计算last=1到3的总和是6，平方和是1+4+9=14。美味值是(36-14)/2=22/2=11，这超过了mid=2。所以必须分割。此时段数变为2，last=3。此时，i=3，处理结束。总共有3段？或者，原数组分成1-2作为第一段，3作为第二段。总段数是2？

哦，可能我这里的例子假设mid=2。那在i=3时，发现1-3段的值是11>2，所以分割，此时段数增加到2，last=3。然后，i继续到4（n=3），循环结束。此时，最后一个段是3，所以总段数是2，符合条件。

那此时总段数是2，所以mid=2是可行的。

所以，这样的分割方式是正确的。

因此，这样的贪心策略是正确的。

现在，回到问题。原题的代码中，给出的代码是否与这个思路一致？

看原题中的check函数：

static long check(long mid){

long count=1;

long sum=0;

int last=1;

for(int i=2;i<=n;i++){

if((sum +a[i]*(prefix[i-1]-prefix[last-1])>mid)){

count++;

last=i;

sum=0;

}else {

sum+=a[i]*(prefix[i-1]-prefix[last-1]);

}

}

return count;

}

这似乎不是正确的计算方式。因为，这里sum的计算方式似乎是在维护不同的东西。比如，这里的sum变量是累加a[i]乘以prefix[i-1]-prefix[last-1]。这可能与原问题的美味值计算方式不符。

比如，原问题的美味值计算式是sum_{i=l}^r sum_{j=i+1}^r a[i]a[j}。这等于总和的平方减去平方和的差除以二。而原代码中的sum变量似乎试图在动态维护这个值，这可能有问题。

例如，假设当前段是last到i-1。现在，处理i，将i加入段中。这时候，新的美味值应该等于原段的sum加上a[i]乘以原段的总和（即prefix[i-1]-prefix[last-1}）。因为，原段的每个元素与a[i]相乘的总和等于（sum_{k=last}^{i-1}a[k]）*a[i}。而这正是新增加的美味值部分。总美味值等于原来的sum加上这个部分。这可能是一个正确的动态维护方法。

例如，假设当前段是last到i-1，此时sum是该段的美味值。当加入i时，新的美味值等于原sum加上a[i] * sum_{k=last}^{i-1} a[k}。因为，原来的段中的每个元素与a[i]相乘，所以新增的项是sum_{k=last}^{i-1} a[k} * a[i}。加上原来的sum，得到新的sum。所以，总美味值等于原sum + a[i] * (prefix[i-1] - prefix[last-1}).

这可能与原问题的美味值的计算方式等价。例如，假设原来的段的美味值为sum，那么当加入a[i]，新的段的美味值等于sum + a[i] * (sum of a[last..i-1}）。

而sum of a[last..i-1}等于prefix[i-1] - prefix[last-1}。所以，这似乎是正确的。

因此，原代码中的sum维护的是当前段的美味值，而每加入一个新的a[i]，sum增加a[i]乘以之前段的总和。这相当于计算两两乘积的总和。这样，是否正确？

举个例子，假设段是1,2，其美味值是1*2=2。当加入3，新的段是1,2,3。美味值应该是1*2 +1*3 +2*3=2+3+6=11。根据原代码的逻辑，sum初始为2（原段的美味值），当加入3时，原段的总和是3（1+2），所以sum增加3*3=9。总和变为2+9=11。这是正确的。所以，原代码中的sum维护方式是正确的。

所以，原代码中的sum变量维护的是当前段的美味值。每次尝试将i加入段时，sum会增加a[i] * (当前段的总和（即prefix[i-1] - prefix[last-1}）)。这样，当sum超过mid时，必须分割。此时，当前段为last到i-1，sum重置为0，新的段从i开始。而由于新的段只有一个元素，它的美味值为0，所以sum=0是正确的。

因此，原代码中的check函数是正确的。那为什么原题中的代码可能有问题？

比如，当段从last到i-1，此时加入i时，计算新增的sum是a[i] * (prefix[i-1] - prefix[last-1}），然后将sum的总和与mid比较。如果总和超过mid，则分割。否则，sum加上这个值，继续。

所以，原代码中的逻辑是正确的。这可能是一个正确的解法。

因此，原题的代码是正确的，但需要确认。

那么，现在回到问题，原题的代码是否正确？或者是否存在错误？

举个例子，假设n=3，m=2，数组为1,2,3。整个数组的美味值是11。假设mid=11的话，分成一段，此时count=1<=2，所以mid=11可能被接受。但正确的答案可能更小。

例如，假设分成1|2,3。第一段的美味值是0，第二段的美味值是2*3=6。最大值是6。或者分成1,2 |3。最大值是2。或者分成1|2|3，此时段数为3，超过m=2。所以当m=2时，最优的分割是分成1,2 |3，最大美味值为2。或者另一种分割方式，如1 | 2,3，最大是6。显然，最优的是分成前两段，得到最大值2。所以正确的输出是2。

那原代码是否能得到正确的结果？

让我们看原代码的check函数：

初始count=1，last=1，sum=0.

i=2:

sum += a[2]*(prefix[1] - prefix[0}) → a[2]=2，prefix[1]是1，prefix[0]是0。所以2*(1-0)=2. sum现在是2. 判断是否超过mid？假设mid是2.

sum是2，等于mid，所以不分割。sum变为2.

i=3：

此时，计算sum + a[3]*(prefix[2] - prefix[last-1}=prefix[2] - prefix[0}=1+2=3. a[3]=3*3=9. sum+9=2+9=11>mid=2。所以必须分割。count增加到2，last=3，sum=0.

循环结束，count=2 <=m=2，返回true。所以此时mid=2被认为是可行的。此时，原代码的二分法会继续寻找更小的mid吗？

二分的过程是：当check(mid)<=m，则r=mid，否则 l=mid+1.

所以，在mid=2时，返回的count是2<=m=2，所以r=mid=2。此时，循环继续，直到l=r=2，所以输出2。这与预期结果一致。

这说明原代码是正确的。

那现在，问题就转化为理解原代码中的check函数如何正确维护sum的值，并且分割正确。

总结：原题的代码是正确的。它使用二分法来寻找最小的最大美味值。在check函数中，通过动态维护当前段的美味值，每次尝试将新的元素加入当前段，如果超过mid则分割。这种方法正确计算了段的美味值，并且贪心地分割，从而得到正确的最小段数。

代码

import java.util.Scanner;public class Main {static int n; // 定义全局变量 n，表示苹果序列的长度static int[] a; // 定义全局数组 a，存储苹果甜度值static long[] prefix; // 定义全局数组 prefix，用于存储前缀和public static void main(String[] args) {Scanner scan = new Scanner(System.in); // 创建 Scanner 对象，用于读取输入n = scan.nextInt(); // 读取输入的第一个整数，赋值给 n（苹果数量）int m = scan.nextInt(); // 读取输入的第二个整数，赋值给 m（分段数）// 初始化数组 a 和 prefix 的大小为 n+10，避免越界a = new int[n + 10];prefix = new long[n + 10];// 输入苹果甜度值，并计算前缀和for (int i = 1; i <= n; i++) {a[i] = scan.nextInt(); // 读取第 i 个苹果的甜度值prefix[i] = prefix[i - 1] + a[i]; // 计算前缀和：prefix[i] = sum(A[1..i])}// 二分查找的初始范围long l = 0, r = Long.MAX_VALUE; // l 表示下界，r 表示上界// 开始二分查找，寻找最小的最大美味值while (l < r) { // 当 l < r 时继续循环long mid = (l + r) >> 1; // 取中间值 mid = (l + r) / 2if (check(mid) <= m) { // 调用 check 函数，判断是否可以分成不超过 m 段r = mid; // 如果可以，则缩小上界 r} else {l = mid + 1; // 否则增大下界 l}}System.out.println(l); // 输出最终结果，即最小的最大美味值scan.close(); // 关闭 Scanner 对象}// 定义 check 函数，用于判断在限制条件下是否可以将序列分成不超过 m 段static long check(long mid) {long count = 1; // 初始化分段数为 1long sum = 0; // 初始化当前段的美味值为 0int last = 1; // 初始化当前段的起始位置为 1// 遍历整个序列，尝试划分满足条件的段落for (int i = 2; i <= n; i++) {// 计算当前苹果对当前段的贡献值long add = a[i] * (prefix[i - 1] - prefix[last - 1]);// 如果当前段的美味值加上新的贡献值超过限制 mid，则新开一段if (sum + add > mid) {count++; // 分段数加 1last = i; // 更新当前段的起始位置为 isum = 0; // 重置当前段的美味值为 0} else {sum += add; // 否则累加当前苹果的贡献值到当前段的美味值}}return count; // 返回分段数}
}