题目描述

有 $n$ 个人，每个人有一个能量值，其中第 $i$ 个人的能量值是 $a_i$，现在需要将这 $n$ 个人组成若干个团队，使
得每个团队的人数不小于 $2$ 且不大于 $k$，当然，每个人只能属于一个团队。

当然，组团队是需要付出金币的，假设编号为 $i$ 的人的能量值是 $a_i$，他所加入的团队成员中的最大能量值是 $max$，那么编号为 $i$ 的人需要付出 $max - a_i$ 个金币。

现在需要你找一种策略，使得每个人都加入了团队并且团队成员人数符合要求，求所有人需要付出金币数量的总和的最小值。

数据保证至少有一种方案使得每个人都加入团队。

输入描述

第一行两个正整数 $n$，$k$。
第二行 $n$ 个正整数 $a_1$, $a_2$....$a_n$，表示每个人的能量值。

$2$ $\leq$ $k$ $\leq$ $n$ $\leq$ $10^6$
$1$ $\leq$ $a_i$ $\leq$ $10^9$

输出描述

一行一个整数，表示需要付出金币数量总和的最小值。

输入样例

5 3
7 1 9 2 9

输出样例

3

斜率优化DP

题目大意：给定一个数组 $a$，数组 $a$是递增的，要求分成若干组，每组个数不少于 $2$ 不大于 $k$，每个组的代价是该组的每个数和最大数的差的和，问代价和的最小值

朴素动态规划：

$f[i]$：表示将前 $i$ 个人加入团队的最小金币数，由于每组人数在 $2 - k$，因此转移方程为：

$$f[i]=\sum_{i-k<j<i}max(f[j - 1] + a[i] * (i - j + 1) - (s[i] - s[j - 1]))$$

于是，我们就可以写出朴素版的DP代码：

C++代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

const int N = 1e6 + 10;
LL a[N];
LL s[N];
LL f[N];    // f[i]：将前 i个人加入团队的最小金币数
int q[N];
int n, k;

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++)   cin >> a[i];

    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i ++)   s[i] = s[i - 1] + a[i];

    memset(f, 0x3f, sizeof f);
    f[0] = 0;

    for (int i = 1; i <= n; i ++)   // 每个团队最少 2个，最多 k个
    {
        for (int j = 0; j < i; j ++)    // [j, i]作为当前的组
            if (j && i - j + 1 <= k)
                f[i] = min(f[i], f[j - 1] + a[i] * (i - j + 1) - (s[i] - s[j - 1]));
    }

    cout << f[n];
    return 0;
}

不理解斜率优化DP的请先做 AcWing 301. 任务安排2 和 AcWing 303. 运输小猫

但是，题目 $n$ 的数据是 $10^6$，$O(n^2)$的时间复杂度肯定过不了，那怎么办呢，这个时候就要用到我们的斜率优化了，我们对方程进行展开：
$$f(i) = f(j - 1) + a[i] * (i - j + 1) - (s[i] - s[j - 1])$$

可以把 $i$ 相关的看成常数，因为当前轮有关 $i$ 的信息都是已知的，除了 $f[i]$ 未知，把和 $j$ 相关的全部看成未知数，移项后：
$$f(j - 1) + s[j - 1] = j * a[i] + (f(i) + s[i] - a[i] * (i + 1))$$

此时，该式可以看成 $y = k*x + b$ 的一元一次方程组

$f(j - 1) + s[j - 1]$ 就是我们的 $y$ ，$j$ 就是我们的 $x$ ，$a[i]$ 就是我们的斜率，后面括起来的一堆就是我们的截距，我们的目标有且只有一个：$f[i]$最小，也就是让截距最小

那如何让截距最小呢，我们可以发现随着 $i$ 的增大，斜率 $a[i]$ 是不断增大的，$j$ 横坐标也在不断增大，形成了一个类似凸包的图形，如下图。

我们可以看成图上已经有若干点对 $(j，y)$，此时新来的线段斜率是 $a[i]$（右边的蓝色的边），我们将蓝色的边依次移动到红色的点上会有一个截距，要让这个截距最小，那也就是说将固定斜率的直线从下往上移动，第一个碰到的点的截距最小，我们可以用一个队列 $q[]$ 维护该凸包的斜率，同时保证队列中的元素不能超过 $k - 1$个。

C++代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

const int N = 1e6 + 10;
LL a[N];
LL s[N];
LL f[N];    // f[i]：将前 i个人加入团队的最小金币数
int q[N];
int n, k;

LL get_y(int j)
{
    return f[j - 1] + s[j - 1];
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i ++)   scanf("%lld", &a[i]);

    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i ++)   s[i] = s[i - 1] + a[i];

    /*
    给定一个数组 a，数组 a是递增的，要求分成若干组，每组个数不少于 2不大于 k，问代价和的最小值

    f(i) = f(j - 1) + a[i] * (i - j + 1) - (s[i] - s[j - 1])

    优化目标：f(i)最小
    f(j - 1) + s[j - 1] = j * a[i] + (f(i) + s[i] - a[i] * (i + 1))
            y           = x * 斜率             截距     

    斜率是递增的，保证截距最小，斜率优化
    */

    memset(f, 0x3f, sizeof f);
    f[0] = 0;

    int hh = 0, tt = 0;
    q[0] = 0;

    for (int i = 1; i <= n; i ++)   // 每个团队最少 2个，最多 k个
    {
        while (hh < tt && (tt - hh + 1 >= k || ((get_y(q[hh + 1]) - get_y(q[hh])) <= 
               a[i] * (q[hh + 1] - q[hh]))))
            hh ++;

        int j = q[hh];
        if (j)
            f[i] = f[j - 1] + a[i] * (i - j + 1) - (s[i] - s[j - 1]);

        while (hh < tt && (get_y(q[tt]) - get_y(q[tt - 1])) * (i - q[tt]) >= 
              (q[tt] - q[tt - 1]) * (get_y(i) - get_y(q[tt])))
            tt --;
        q[ ++ tt] = i;
    }

    printf("%lld\n", f[n]);
    return 0;
}