Luogu | P3620 [APIO / CTSC 2007] 数据备份 | 贪心


Description

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

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

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

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

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

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


Input Format

输入文件的第一行包含整数 $n$ 和 $K$,其中 $n$ 表示办公楼的数目,$K$ 表示可利用的网络电缆的数目。

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


Output Format

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


Input Sample

Sample 01

5 2
1
3
4
6
12


Output Sample

Sample 01

4


Data Range

$1 \le n \le 10^5$。$1 \le s \le 10^9$。


Solution

简单分析一下,容易得到将一条电缆跨过一些建筑安装不可能是最优解。

于是考虑将每两个建筑之间的空隙差分出来,得到 $n-1$ 个值,题意转变为从 $n-1$ 个值中选择 $K$ 个值使得总和最小,且不能选相邻的值。

显然可以 $\Theta(nK)$ 动态规划。只能得到 60 分。

考虑贪心。若某个值为当前序列中的最小值,答案只有可能取这个值,或者取这个值相邻的两个值(?)所以建立一个小根堆存放每个点的值,每次取出最小的未选的两点 $x$,然后将 $x$ 左右未选的两点 的权值减去 $x$ 的权值加入堆,并标记那两个点为已选。这模拟了一个选择的过程:若选 $x$ 是最优解,则不会选到新加进去的那个点;若选 $x$ 左右未选的两点 是最优解,则会选到新加入的点,并消除选 $x$ 的贡献。可以用双向链表维护。

以及,此题似乎可以斜率优化。


Code

#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

using std::priority_queue;

int buf[20];

template <class T> inline void Read(T &x){
    x=0;
    char ch=0;
    bool neg=0;
    while(ch<'0'||ch>'9')
        ch=getchar(),neg|=(ch=='-');
    while(ch>='0'&&ch<='9')
        x=x*10+ch-48,ch=getchar();
    x*=neg?-1:1;
    return;
}

template <class T> inline void Write(T x){
    if(!x){
        putchar('0');
        putchar('\n');
        return;
    }
    if(x<0){
        x=-x;
        putchar('-');
    }
    int cntr=0;
    while(x)
        buf[++cntr]=x%10,x/=10;
    for(int i=cntr;i;i--)
        putchar(buf[i]+48);
    putchar('\n');
    return;
}

struct lnk{
    int prec;
    int val;
    int succ;
}e[100005];

struct data{
    int id;
    int val;
    friend bool operator < (data a,data b){
        return a.val>b.val;
    }
};

int N;
int K;
int ans;

int src[100005];
int dlt[100005];

bool mark[100005]; 

priority_queue<data>pq;

int main(){
    Read(N);
    Read(K);
    rep(i,1,N)
        Read(src[i]);
    rep(i,2,N)
        dlt[i-1]=src[i]-src[i-1];
    src[0]=src[N]=0x3f3f3f3f;
    e[0]=(lnk){0,0x3f3f3f3f,1};
    e[N]=(lnk){N-1,0x3f3f3f3f,N};
    rep(i,1,N-1){
        e[i].prec=i-1;
        e[i].succ=i+1;
        e[i].val=dlt[i];
        pq.push((data){i,dlt[i]});
    }
    rep(i,1,K){
        data x=pq.top(); pq.pop();
        while(mark[x.id]){
            x=pq.top(); pq.pop();
        }
        ans+=x.val;
        mark[e[x.id].prec]=1;
        mark[e[x.id].succ]=1;
        e[x.id].val=e[e[x.id].prec].val+e[e[x.id].succ].val-x.val;
        e[x.id].prec=e[e[x.id].prec].prec;
        e[x.id].succ=e[e[x.id].succ].succ;
        e[e[x.id].prec].succ=x.id;
        e[e[x.id].succ].prec=x.id;
        pq.push((data){x.id,e[x.id].val});
    }
    printf("%d\n",ans);
    return 0;
}