[BZOJ2288&BZOJ1150]一类堆+链表+贪心问题

今天我们来介绍一系列比较经典的堆+链表问题.这类问题的特点是用堆选取最优解,并且通过一些加减操作来实现"反悔".

在看题之前,我们先来介绍一个神器:手写堆.

手写堆的一大好处就是可以可以访问,或者删除堆中的某个特定元素.

手写堆其实就是在模拟二叉堆的比较大小过程,比如:

inline void up(int id)
{
    if(id==1)return;
    if(h[id>>1]<h[id])
        swap(h[id>>1],h[id]),up(id>>1);
}
inline void down(int id)
{
    id<<=1;if(id>top)return;
    if(id<top&&h[id^1]>h[id])id^=1;
    if(h[id>>1]<h[id])
        swap(h[id>>1],h[id]),down(id);
}

这样我们已经可以查找最值了.如果我们想删除某个值,就直接把它的权值设为无穷大/小,再调用down函数.

如果我们还想支持查询某个标号对应的值(下面两个题都会用到)

可以多加一个match数组记录编号.当然,这里的h既要记录编号又要记录权值.

完整的像这样,当然,读者可以结合自己的风格打出自己的手写堆:

int match[N],top;
struct node
{
    int val,pos;
    node(int a=0,int b=0){val=a,pos=b;}
}h[N];
inline void up(int i)
{
    while(i>1&&h[i].val<h[i>>1].val)
        match[h[i>>1].pos]=i,swap(h[i>>1],h[i]),i>>=1;
    match[h[i].pos]=i;
}
inline void down(int i)
{
    int to;
    while((i<<1)<=top)
    {
        to=(i<<1);if(to<top&&h[to+1].val<h[to].val)++to;
        if(h[to].val<h[i].val)
            match[h[to].pos]=i,swap(h[i],h[to]),i=to;
        else break;
    }
    match[h[i].pos]=i;
}
inline void push(int val,int pos)
    {h[++top]=node(val,pos);up(top);}
inline void pop(int i)
    {h[i].val=inf;down(i);}

拿到了我们的强力武器,话不多说,我们先看一道题:

1150: [CTSC2007]数据备份Backup

Time Limit: 10 Sec  Memory Limit: 162 MB

Description

　　你在一家 IT 公司为大型写字楼或办公楼（offices）的计算机数据做备份。然而数据备份的工作是枯燥乏味的，因此你想设计一个系统让不同的办公楼彼此之间互相备份，而你则坐在家中尽享计算机游戏的乐趣。已知办公楼都位于同一条街上。你决定给这些办公楼配对（两个一组）。每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。然而，网络电缆的费用很高。当地电信公司仅能为你提供 K 条网络电缆，这意味着你仅能为 K 对办公楼（或总计2K个办公楼）安排备份。任一个办公楼都属于唯一的配对组（换句话说，这 2K 个办公楼一定是相异的）。此外，电信公司需按网络电缆的长度（公里数）收费。因而，你需要选择这 K 对办公楼使得电缆的总长度尽可能短。换句话说，你需要选择这 K 对办公楼，使得每一对办公楼之间的距离之和（总距离）尽可能小。下面给出一个示例，假定你有 5 个客户，其办公楼都在一条街上，如下图所示。这 5 个办公楼分别位于距离大街起点 1km, 3km, 4km, 6km 和 12km 处。电信公司仅为你提供 K=2 条电缆。　　上例中最好的配对方案是将第 1 个和第 2 个办公楼相连，第 3 个和第 4 个办公楼相连。这样可按要求使用 K=2 条电缆。第 1 条电缆的长度是 3km-1km=2km ，第 2 条电缆的长度是 6km-4km=2km。这种配对方案需要总长 4km 的网络电缆，满足距离之和最小的要求。

Input

　　输入的第一行包含整数n和k，其中n（2 ≤ n ≤100 000）表示办公楼的数目，k（1≤ k≤ n/2）表示可利用的网络电缆的数目。接下来的n行每行仅包含一个整数（0≤ s ≤1000 000 000）, 表示每个办公楼到大街起点处的距离。这些整数将按照从小到大的顺序依次出现。

Output

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

Sample Input

5 2
1
3
4
6
12

Sample Output

4     我们简单抽象一个模型:题意等价于在n-1个物品(len[i]-len[i-1])中选择k个,使得k个物品不相邻. 如果没有不相邻的条件,我们只要选前k小的即可了;但是k个物品需要不相邻...... 每次我们选择的时候，相当于“多选了一段” 如果我们选了第i个权值,那么第i-1个和第i+1个都不能选了,那么我们就用上面的手写堆删掉i-1和i+1对应的元素. 但是有可能由于由于某些奇怪的原因,我们需要反悔,选已经被我们删掉的段(比如4 2 1 2 选2个 选2 2就比1 4小) 那么我们考虑,增加的权值delta=val[i-1]+val[i+1]-val[i],那么我们依然用i代表这个节点,把i的权值改成delta再塞回去即可.
然后,如果我们又选到了节点i,这时候再给ans加上它的val,我们实质上选了val[i-1]和val[i+1]， 这时候选的段数就多了1如果没选到这样的节点，选的段数也会多1， 所以这样进行k次我们就可以统计答案了. 我们再考虑又选到了节点i的情况,显然,i-1和i+1已经没了,我们就要去考虑i+2和i-2了； 如果一直这样选择,这个东西符合双向链表的特点(不断扩展), 所以我们就用双向链表维护每个段i左面和右面第一个未被删除的节点. 对于i+2和i-2，所以这时候新的权值是val[i+2]+val[i-2]-(val[i-1]+val[i+1]-val[i]),它的本质是选择val[i],val[i-2]和val[i+2]又多了一段 还有一个特别注意的地方:边界处理. 如果我们目前选择的元素i的某个边界没有元素了（也就是说选到了头），那么我们再反悔的话，会变成这样：   我们发现，如果这时候“反悔”的话，长度不会增加，事实上，任何情况下，选三角都没有选对勾优秀。 因为我在不断贪心，如果选三角优我应该先统计了三角的答案了 比如说1 2 3 4，选了1，显然没有必要把0+2-1再扔回去啊 所以我们把它的答案统计上直接扔掉就可以了，它不能继续扩展了 那么这样我们就解决了这道题。代码见下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010,inf=0x7fffffff;
int n,m,s[N],d[N],cnt,top;
int match[N];
struct node
{
    int val,pos;
    node(int a=0,int b=0){val=a,pos=b;}
}h[N];
inline void up(int i)
{
    while(i>1&&h[i].val<h[i>>1].val)
        match[h[i>>1].pos]=i,swap(h[i>>1],h[i]),i>>=1;
    match[h[i].pos]=i;
}
inline void down(int i)
{
    int to;
    while((i<<1)<=top)
    {
        to=(i<<1);if(to<top&&h[to+1].val<h[to].val)++to;
        if(h[to].val<h[i].val)
            match[h[to].pos]=i,swap(h[i],h[to]),i=to;
        else break;
    }
    match[h[i].pos]=i;
}
inline void push(int val,int pos)
    {h[++top]=node(val,pos);up(top);}
inline void pop(int i)
    {h[i].val=inf;down(i);}
int pre[N],nxt[N];
int main()
{
    register int i,j,k;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)scanf("%d",&s[i]);
    for(i=1;i<n;++i)d[i]=s[i+1]-s[i],push(d[i],i);
    for(i=1;i<n;++i)pre[i]=i-1,nxt[i]=i+1;
    nxt[n-1]=0;
    node x;int l,r,ans=0;
    for(i=1;i<=m;++i)
    {
        x=h[1];ans+=x.val;
        l=pre[x.pos],r=nxt[x.pos];
        if(!l) pop(1),pop(match[r]),pre[nxt[r]]=0;
        else if(!r) pop(1),pop(match[l]),nxt[pre[l]]=0;
        else
            h[1].val=h[match[l]].val+h[match[r]].val-h[1].val,
            pre[x.pos]=pre[l],nxt[pre[l]]=x.pos,
            nxt[x.pos]=nxt[r],pre[nxt[r]]=x.pos,
            pop(match[l]),pop(match[r]),down(1);
    }
    printf("%d\n",ans);
}

下面我们再来看另外一道题，套路是相似的，但是更加有挑战性：

2288: 【POJ Challenge】生日礼物

Time Limit: 10 Sec  Memory Limit: 128 MB

Description

ftiasch 18岁生日的时候，lqp18_31给她看了一个神奇的序列 A₁, A₂, ..., A_N. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。

自然地，ftiasch想要知道选择元素之和的最大值。你能帮助她吗？

Input

第1行，两个整数 N (1 ≤ N ≤ 10⁵) 和 M (0 ≤ M ≤ 10⁵), 序列的长度和可以选择的部分。

第2行， N 个整数 A₁, A₂, ..., A_N (0 ≤ |A_i| ≤ 10⁴), 序列。

Output

一个整数，最大的和。

Sample Input

5 2
2 -3 2 -1 2

Sample Output

5 题解：（施工ing。。。。。）