题目传送门
[题目大意]
有 $n$ 座房子在一条街上, 给出每座房子距起点的距离, 现在有 $k$ 根电缆可以把两个房子连接起来. 保证每座房子至多只会与一座房子相连, 求最短的电缆总长度.
[思路分析]
相当于看成 $n-1$ 个物品, 每个物品有一个权值 (即两座房子之间的距离), 要求不能取相邻的物品, 求取出 $k$ 个物品的最小权值之和.
我们用一个堆将这 $n-1$ 个物品从小到大排序, 堆顶为权值最小的. 假设现在取了堆顶的物品 $a_i$, 如果我们同时选 $a_{i-1},a_{i+1}$ 才有可能更优, 如果单选 $a_{i-1}$ 或 $a_{i+1}$ 一定不会更优, 因为 $a_i$ 在堆顶就已经保证了 $a_i$ 是当前最小值. 如果不选 $a_i$ 而改选 $a_{i-1}$ 和 $a_{i+1}$, 那么总答案加上 $a_{i-1}+a_{i+1}-a_i$, 此时我们可以把堆中的 $a_{i-1}$ 和 $a_{i+1}$ 删除, 插入一个权值为 $a_{i-1}+a_{i+1}-a_i$ 的新物品, 同时更新链表的值, 把 $a_{i-1},a_i,a_{i+1}$ 当作一个物品处理.
[代码实现]
- #include<cstdio>
- #include<iostream>
- #include<cstring>
- #include<algorithm>
- #include<cmath>
- #include<queue>
- #define g() getchar()
- #define rg register
- #define go(i,a,b) for(rg int i=a;i<=b;i++)
- #define back(i,a,b) for(rg int i=a;i>=b;i--)
- #define db double
- #define ll long long
- #define il inline
- #define pf printf
- using namespace std;
- ll fr(){
- ll w=0,q=1;
- char ch=g();
- while(ch<'0'||ch>'9'){
- if(ch=='-') q=-1;
- ch=g();
- }
- while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=g();
- return w*q;
- }
- const int N=100002;
- const int INF=1e9+7;
- ll n,k,a[N],L[N],R[N],s[N],ans;//L,R 记录链表位置
- bool vis[N];
- struct node{
- int id;ll data;
- }p;
- priority_queue<node> q;// 用堆维护一下
- il bool operator <(node x,node y){return x.data>y.data;}// 重载运算符
- int main(){
- //freopen("","r",stdin);
- //freopen("","w",stdout);
- n=fr();k=fr();
- go(i,0,n-1){
- s[i]=fr();
- if(i){
- p=(node){i,a[i]=s[i]-s[i-1]};
- q.push(p);
- L[i]=i-1;R[i]=i+1;
- }
- }
- R[0]=1;L[n]=n-1;a[0]=a[n]=INF;
- while(k--){
- while(vis[q.top().id]) q.pop();
- node t=q.top();q.pop();
- rg int pos=t.id;
- ans+=t.data;
- t.data=a[pos]=a[L[pos]]+a[R[pos]]-a[pos];
- q.push(t);
- vis[L[pos]]=vis[R[pos]]=1;
- L[pos]=L[L[pos]];R[pos]=R[R[pos]];
- R[L[pos]]=L[R[pos]]=pos;
- }
- pf("%lld\n",ans);
- return 0;
- }
代码戳这里
来源: http://www.bubuko.com/infodetail-3203501.html