SP1553 BACKUP - Backup Files 题解

题意：

你在一家 IT 公司为大型写字楼或办公楼的计算机数据做备份。然而数据备份的工作是枯燥乏味的，因此你想设计一个系统让不同的办公楼彼此之间互相备份，而你则坐在家中尽享计算机游戏的乐趣。

已知办公楼都位于同一条街上。你决定给这些办公楼配对（两个一组）。每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。

然而，网络电缆的费用很高。当地电信公司仅能为你提供 $k$ 条网络电缆，这意味着你仅能为 $k$ 对办公楼（或总计 $2k$ 个办公楼）安排备份。任一个办公楼都属于唯一的配对组（换句话说，这 $2k$ 个办公楼一定是相异的）。

此外，电信公司需按网络电缆的长度（公里数）收费。因而，你需要选择这 $k$ 对办公楼使得电缆的总长度尽可能短。换句话说，你需要选择这 $k$ 对办公楼，使得每一对办公楼之间的距离之和（总距离）尽可能小。

下面给出一个示例，假定你有 $5$ 个客户，其办公楼都在一条街上，如下图所示。这 $5$ 个办公楼分别位于距离大街起点 1km, 3km, 4km, 6km 和 12km 处。电信公司仅为你提供 $k=2$ 条电缆。

上例中最好的配对方案是将第 1 个和第 2 个办公楼相连，第 3 个和第 4 个办公楼相连。这样可按要求使用 $k=2$ 条电缆。第 1 条电缆的长度是 3km - 1km = 2km，第 2 条电缆的长度是 6km - 4km = 2km。这种配对方案需要总长 4km 的网络电缆，满足距离之和最小的要求。

输入格式：

本题有多组数据。

每组输入文件的第一行包含整数 $n$ 和 $k$，其中 $n~(1\le n\le 10^5)$ 表示办公楼的数目，$k~(1\le k\le \frac{n}{2})$ 表示可利用的网络电缆的数目。

接下来的 $n$ 行每行仅包含一个整数 $(0\le s\le 10^9)$ ，表示每个办公楼到大街起点处的距离。

这些整数将按照从小到大的顺序依次出现。

输出格式：

每组输出文件应当由一个正整数组成，给出将 2K 个相异的办公楼连成 K 对所需的网络电缆的最小总长度。

记 $w_i = a_{i + 1} - a_i$ ，问题就变成选 $k$ 对，容易设计出 dp 方程。

显然这个 dp 方程是一个凸函数，考虑 wqs 二分即可。检验的话也是一个简单 dp 。

时间复杂度 $\mathcal{O}(n \log V)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(5e5 + 15))

int n, k, res, a[N], dp[N][2], cnt[N][2];
bool check(int x)
{
    rep(i, 1, n) { dp[i][0] = dp[i][1] = 0; cnt[i][0] = cnt[i][1] = 0; }
    dp[1][1] = a[1] - x; cnt[1][1] = 1;
    rep(i, 2, n)
    {
        dp[i][1] = dp[i - 1][0] + a[i] - x;
        cnt[i][1] = cnt[i - 1][0] + 1;
        if(dp[i - 1][1] < dp[i - 1][0]) {
            dp[i][0] = dp[i - 1][1]; cnt[i][0] = cnt[i - 1][1];
        }else {
            dp[i][0] = dp[i - 1][0]; cnt[i][0] = cnt[i - 1][0];
        }
    }
    if(dp[n][1] < dp[n][0]) { 
        res = dp[n][1]; return cnt[n][1] <= k;
    }else { 
        res = dp[n][0]; return cnt[n][0] <= k; 
    }
}
void solve()
{
    res = 0; cin >> n >> k;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, --n) a[i] = a[i + 1] - a[i];
    int l = 0, r = 1e9;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1; ;
        if(check(mid)) l = mid; else r = mid - 1;
    }
    check(l); cout << res + l * k << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}