题解 SP1553 【BACKUP - Backup Files】

· · 题解

SP1553题解

传送门

题目分析

容易发现，最优解中相邻两个办公楼一定是相邻的，我们求出每相邻两个办公楼之间的距离a，记为 a_1,a_2,a_3 … a_{N-1} ，那么问题可以转化为从数组a中选出不超过K个数，使他们的和最小，并且相邻两个数不能同时被选。

这样本题就被转化为了P1484 （不过P1484是一个环这是一条链，而且本题有多组数据）

比如样例就可以被转化为 2,1,2,6 ，那么我们选择第一个和第三个2，就得到了最优解4。

解题思路

如果 K = 1，那么结果就是a数组中的最小值。

如果 K = 2，那么就有两种情况：

  1. 选择最小值 a_i ，不选 a_{i-1} ,a_{i+1} ，再从剩下的数中选择最小值。
  2. 不选最小值 a_i ，选 a_{i-1} ,a_{i+1} 。

为什么不选最小值 a_i 就要选 a_{i-1} ,a_{i+1} 呢？

如果只选了 a_{i-1} ,a_{i+1} 中的一个，那么把选了的换成了 a_i 一定更优。

显然a_i , a_{i-1} ,a_{i+1} 都不选不是最优解。

所以最小值左右两侧的数要么都选，要么都不选。

所以我们可以先选上 a 数组中的最小值（第一种情况），然后将然后将 a_{i-1},a_i,a_{i+1} 从数列中删除，并在原位置插入一个新元素a_{i-1}-a_i+a_{i+1} 。这样原问题就变成了一个从 a数组中选 K-1 的数的子问题，显然重复这个操作 k-1次就可以求出最终结果。

代码实现思路

所以我们可以建立一个链表 Q，分别记录a_1,a_2,a_3 … a_{N-1} 。 再建立一个二元组小根堆，每个元素与链表中的每一个元素成一一映射关系，第二元记录对应链表中的指针。

每次取出堆顶，更新答案。再删除节点（链表中打标记、更新左右节点数组，小根堆中删除）、插入新节点。

执行K次后输出

易错点

AC代码

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
void read(int &x){
    int f=1;x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
#define N 100010
priority_queue < pair <ll,int > > q;
int n,k,le[N],r[N],t;
bool v[N];
long long ans,a[N];
void del(int x){
    le[r[x]]=le[x];
    r[le[x]]=r[x];
    v[x]=1;
}
int main(){
    read(t);
    while(t--){
    memset(le,0,sizeof(le));
    memset(r,0,sizeof(r));
    memset(v,0,sizeof(v));
    memset(a,0,sizeof(a));
    while(q.size()) q.pop();
    ans=0;
    read(n),read(k);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    n--;
    //le[1]=n,le[n]=n-1,r[1]=2,r[n]=1;
    for(int i=1;i<=n;i++){
        le[i]=i-1,r[i]=i+1;
        a[i]=a[i+1]-a[i];
        q.push(make_pair(-a[i],i));
    }
    a[0]=a[n+1]=1234567890;
    while(k--){
        int x,y;
        while(v[q.top().second]) q.pop();
        x=q.top().second;q.pop();
        ans+=a[x];
        //printf("%lld %d\n",ans,x);
        a[x]=a[le[x]]+a[r[x]]-a[x];
        v[x]=0;
        del(le[x]),del(r[x]);
        q.push(make_pair(-a[x],x));
    }
    cout<<ans<<endl;
    }
    return 0;
}