题目如下
数据范围
示例
题目的意思是将一个长度为n的数组weight(简称w)分成k个小数组,同时计算这些小数组的边界和。
设i (0 <= i <= n - 1)
首先我们假设已经找到最大分数序列即划分的小数组最优 令 j1,j2,j3.....jk为这些小数组的左端点(不包括第一个小数组)。
则有
max = (w[0] + w[j1 - 1]) + (w[j1] + w[j2 - 1]) + (w[j2] + w[j3 - 1]) + ....... +
+ (w[jk] + w[n - 1])
同理
min = w[0] + .... + w[n - 1]
ans = max - min
可以看出真正影响结果的是排除w[0]和w[n - 1]之后的和。
显然排除w[0],w[n - 1]得到的是相邻两点之和总数k - 1 。
所以本题转换为求最大k - 1个的相邻和减去最小k - 1的相邻和。
如果不理解可以随便构造一个数组任取k - 1个相邻和加上首项和尾项看看是不是能写成k个区间,显然是可以的。
所以本题只需要将数组相邻和求出来排序就能得到答案。
通过代码
class Solution {
public:long long putMarbles(vector<int>& weights, int k) {int n = weights.size();long long min = 0,max = 0;if(n == k)return 0;vector<int> sum;for(int i = 1;i < n;i++)sum.push_back(weights[i] + weights[i - 1]);sort(sum.begin(),sum.end());k--;for(int i = 0;i < k;i++)min += sum[i];for(int i = n - 2;i > n - k - 2;i--)max += sum[i];return max - min;}
};
