今天我们来介绍一系列比较经典的堆+链表问题.这类问题的特点是用堆选取最优解,并且通过一些加减操作来实现"反悔".
在看题之前,我们先来介绍一个神器:手写堆.
手写堆的一大好处就是可以可以访问,或者删除堆中的某个特定元素.
手写堆其实就是在模拟二叉堆的比较大小过程,比如:
inline void up(int id)
{
if(id==)return;
if(h[id>>]<h[id])
swap(h[id>>],h[id]),up(id>>);
}
inline void down(int id)
{
id<<=;if(id>top)return;
if(id<top&&h[id^]>h[id])id^=;
if(h[id>>]<h[id])
swap(h[id>>],h[id]),down(id);
}
这样我们已经可以查找最值了.如果我们想删除某个值,就直接把它的权值设为无穷大/小,再调用down函数.
如果我们还想支持查询某个标号对应的值(下面两个题都会用到)
可以多加一个match数组记录编号.当然,这里的h既要记录编号又要记录权值.
完整的像这样,当然,读者可以结合自己的风格打出自己的手写堆:
int match[N],top;
struct node
{
int val,pos;
node(int a=,int b=){val=a,pos=b;}
}h[N];
inline void up(int i)
{
while(i>&&h[i].val<h[i>>].val)
match[h[i>>].pos]=i,swap(h[i>>],h[i]),i>>=;
match[h[i].pos]=i;
}
inline void down(int i)
{
int to;
while((i<<)<=top)
{
to=(i<<);if(to<top&&h[to+].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
Input
Output
输出应由一个正整数组成,给出将2K个相异的办公楼连成k对所需的网络电缆的最小总长度。
Sample Input
1
3
4
6
12
Sample Output
然后,如果我们又选到了节点i,这时候再给ans加上它的val,我们实质上选了val[i-1]和val[i+1],
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=,inf=0x7fffffff;
int n,m,s[N],d[N],cnt,top;
int match[N];
struct node
{
int val,pos;
node(int a=,int b=){val=a,pos=b;}
}h[N];
inline void up(int i)
{
while(i>&&h[i].val<h[i>>].val)
match[h[i>>].pos]=i,swap(h[i>>],h[i]),i>>=;
match[h[i].pos]=i;
}
inline void down(int i)
{
int to;
while((i<<)<=top)
{
to=(i<<);if(to<top&&h[to+].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=;i<=n;++i)scanf("%d",&s[i]);
for(i=;i<n;++i)d[i]=s[i+]-s[i],push(d[i],i);
for(i=;i<n;++i)pre[i]=i-,nxt[i]=i+;
nxt[n-]=;
node x;int l,r,ans=;
for(i=;i<=m;++i)
{
x=h[];ans+=x.val;
l=pre[x.pos],r=nxt[x.pos];
if(!l) pop(),pop(match[r]),pre[nxt[r]]=;
else if(!r) pop(),pop(match[l]),nxt[pre[l]]=;
else
h[].val=h[match[l]].val+h[match[r]].val-h[].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();
}
printf("%d\n",ans);
}
下面我们再来看另外一道题,套路是相似的,但是更加有挑战性:
2288: 【POJ Challenge】生日礼物
Time Limit: 10 Sec Memory Limit: 128 MB
Description
ftiasch 18岁生日的时候,lqp18_31给她看了一个神奇的序列 A1, A2, ..., AN. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。
自然地,ftiasch想要知道选择元素之和的最大值。你能帮助她吗?
Input
第1行,两个整数 N (1 ≤ N ≤ 105) 和 M (0 ≤ M ≤ 105), 序列的长度和可以选择的部分。
第2行, N 个整数 A1, A2, ..., AN (0 ≤ |Ai| ≤ 104), 序列。
Output
一个整数,最大的和。
Sample Input
2 -3 2 -1 2