问题描述

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

已知办公楼都位于同一条街上。你决定给这些办公楼配对(两个一组)。每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。然而,网络电缆的费用很高。当地电信公司仅能为你提供 K 条网络电缆,这意味着你仅能为 K 对办公楼(或总计2K个办公楼)安排备份。任一个办公楼都属于唯一的配对组(换句话说,这 2K 个办公楼一定是相异的)。此外,电信公司需按网络电缆的长度(公里数)收费。

因而,你需要选择这 K 对办公楼使得电缆的总长度尽可能短。换句话说,你需要选择这 K 对办公楼,使得每一对办公楼之间的距离之和(总距离)尽可能小。

输入

第一行包含整数n和k。
其中n(2≤n≤100000)表示办公楼的数目,k(1≤k≤n/2)表示可利用的网络电缆的数目。

接下来的n行每行仅包含一个整数(0≤s≤1000000000),表示每个办公楼到大街起点处的距离。这些整数将按照从小到大的顺序依次出现。

输出

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

思路

第一眼看题,想着用网络流去做QWQ。

想了一下后,突然想起一道题BZOJ2151 种树。当时做这道题时觉得这道题的思路十分巧妙。然后这道题也可以用一模一样的思路去做。

每次贪心选取最大值,答案加上这个最大值,最大值左右两边当然不能再选,于是就标记为访问过。

但是这个贪心显然是不完善的。当最大值左右两边之和大于它本身时,就会产生错误。于是就有一种神奇的操作:将左右两边之和减去最大值,作为新的节点,覆盖掉原来的最大值,并删去左右两个节点。

原因是要么选最大值,要么选它的左右之和,选最大值时答案加上这个最大值,不再去选新的节点,选左右之和时答案还是加上最大值,只不过后面还要加上新节点的值。也就是当我们再次选取的新节点时,也就相当于选取当时最大值的左右之和,而没有选最大值。

细节

  1. 要注意链头和链尾要特殊处理;
  2. 要注意删除操作的顺序;
  3. 访问过的节点dis要标记为INF.

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define LL long long
#define INF 0x7fffffff
#define MAXN 100005
using namespace std;

struct Sec
{
    LL dis, pos;
    bool operator < (const Sec &x) const
    {
        return dis>x.dis;
    }
} sec[MAXN];

LL n, k, ans, x[MAXN], dis[MAXN], pre[MAXN], nxt[MAXN];

priority_queue<Sec> q;

int main()
{
    scanf("%lld%lld", &n, &k);
    for(int i=1; i<=n; i++) scanf("%lld", &x[i]);
    for(int i=2; i<=n; i++)
    {
        dis[i]=x[i]-x[i-1];
        q.push((Sec) {dis[i], i});
        pre[i]=i-1; nxt[i]=i+1;
    }
    pre[2]=0; nxt[n]=0;
    for(int i=1; i<=k; i++)
    {
        while(dis[q.top().pos]==INF) q.pop();
        LL pos=q.top().pos; q.pop();
        ans+=dis[pos];
        if(!nxt[pos]) //处理链尾
        {
            dis[pre[pos]]=INF;
            nxt[pre[pos]]=0;
            continue;
        }
        if(!pre[pos]) //处理链头
        {
            dis[nxt[pos]]=INF;
            pre[nxt[pos]]=0;
            continue;
        }
        dis[pos]=dis[pre[pos]]+dis[nxt[pos]]-dis[pos];
        dis[pre[pos]]=dis[nxt[pos]]=INF;
        pre[pos]=pre[pre[pos]];
        nxt[pos]=nxt[nxt[pos]];
        pre[nxt[pos]]=nxt[pre[pos]]=pos;
        q.push((Sec){dis[pos], pos});
    }
    printf("%lld\n", ans);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注