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

题解 数据结构-堆 省选/NOI-
题目链接 编辑文章

四倍经验(1蓝2紫1黑):P3620SP1553P1484P1792

题意

将 $N$ 个办公楼两两配成 $K$ 对,要求这 $K\times 2$ 栋楼相异。所有办公楼在一条直线上,配对的两栋楼之间需要连接电缆,求电缆长度的最小值。

$N\le 100000$ 。

题解

显然,配对相邻的两栋楼是最优的。将边看成点来考虑,题目即转化成:在 $N$ 个点中选 $K$ 个不相邻的点,使得点权最小。

每次选点的最优策略只有两种:

  1. 选最小的点
  2. 把最小的点左右两侧的点都选上

如果不选最小的点,在左右两侧只选一个的话显然是不如直接选最小点的。

实现就是每次取最小的点 $S_i$ ,把该点的值替换为 $S_{i-1}+S_{i+1}-S_i$ ,并把它左右节点删除。如果后续又选到的这个点,就相当于最初选了左右两侧的点。

删除就用数组模拟链表,并记录哪些点被删就行了。

#include<bits/stdc++.h>
#define pr pair<int,int>
#define mp make_pair

using namespace std;

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

bool d[100005];
int n,k,ans,s[100005],l[100005],r[100005];
priority_queue <pr,vector<pr>,greater<pr> > q;

inline void del(int x) //删除点
{
    d[x]=1;
    l[r[x]]=l[x];
    r[l[x]]=r[x];
}

signed main()
{
    n=read(); k=read();
    for (int i=1;i<=n;i++) s[i]=read();
    for (int i=1;i<n;i++) s[i]=s[i+1]-s[i],l[i]=i-1,r[i]=i+1;
    s[0]=s[n]=1e9;
    for (int i=1;i<n;i++) q.emplace(mp(s[i],i));
    for (int i=1;i<=k;i++)
    {
        int x=q.top().first,y=q.top().second; q.pop();
        if (d[y]) { i--; continue; } //被删则跳过
        ans+=x;
        s[y]=s[l[y]]+s[r[y]]-s[y];
        q.emplace(mp(s[y],y));
        del(l[y]); del(r[y]);
    }
    return !printf("%d",ans);
}

还有三倍经验

  1. SP1553:改下多组数据就行了,注意数组清空。
  2. P1484:直接给出点,而且是求最大。注意不一定要用完,所以当前堆顶 $<0$ 就直接退出。
  3. P1792:也是直接给出点,不过是环形的,需要修改一下 $1$ 和 $n$ 的前驱后继。还有如果 $\dfrac{n}{2}<k$ 要输出 Error!

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空

第一次提交的评论将在审核后显示。