M_sea

洛谷3620 [APIO/CTSC 2007]数据备份
LuoguBZOJ分析有两条性质:最优解中每对办公楼是相邻的。所以设$d[i]$表示$i$与$i+1$之间的距离。...
扫描右侧二维码阅读全文
07
2018/12

洛谷3620 [APIO/CTSC 2007]数据备份

Luogu

BZOJ

分析

有两条性质:

最优解中每对办公楼是相邻的。

所以设$d[i]$表示$i$与$i+1$之间的距离。

在最优解中,最小值左右两侧的数要么都选,要么都不选。

然后每次就可以找到$d$中最小值$d[i]$,然后把$d[i-1],d[i],d[i+1]$删掉,再把$d[i-1]+d[i+1]-d[i]$插入到删除的位置。

把这个过程做$k$遍就好了。

找最小值可以维护一个堆,需要打删除标记;然后还需要维护一个链表。

注意一些细节。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100000+10;

struct HeapNode {
    int val,ind;
    bool operator <(const HeapNode& rhs) const {
        return val>rhs.val;
    }
};

priority_queue<HeapNode> Q;
int a[MAXN];
int d[MAXN<<1],pre[MAXN<<1],nxt[MAXN<<1];
int del[MAXN<<1];

int main() {
    int n=read(),k=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<n;++i) {
        d[i]=a[i+1]-a[i],pre[i]=i-1,nxt[i]=i+1;
        Q.push((HeapNode){d[i],i});
    }
    pre[1]=nxt[n-1]=0; d[0]=1e9;
    int ans=0,cnt=n-1;
    for (re int i=1;i<=k;++i) {
        while (!Q.empty()&&del[Q.top().ind]) Q.pop();
        if (Q.empty()) break;
        HeapNode fr=Q.top(); Q.pop();
        int ind=fr.ind,val=fr.val;
        ans+=val;
        del[ind]=del[pre[ind]]=del[nxt[ind]]=1;
        d[++cnt]=d[pre[ind]]+d[nxt[ind]]-d[ind];
        pre[cnt]=pre[pre[ind]],nxt[pre[cnt]]=cnt;
        nxt[cnt]=nxt[nxt[ind]],pre[nxt[cnt]]=cnt;
        Q.push((HeapNode){d[cnt],cnt});
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 12 月 07 日 10 : 22 PM

发表评论