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

时间:2020-12-23 12:11:33

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

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

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

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

 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

  你在一家 IT 公司为大型写字楼或办公楼(offices)的计算机数据做备份。然而数据备份的工作是枯燥乏味
的,因此你想设计一个系统让不同的办公楼彼此之间互相备份,而你则坐在家中尽享计算机游戏的乐趣。已知办公
楼都位于同一条街上。你决定给这些办公楼配对(两个一组)。每一对办公楼可以通过在这两个建筑物之间铺设网
络电缆使得它们可以互相备份。然而,网络电缆的费用很高。当地电信公司仅能为你提供 K 条网络电缆,这意味
着你仅能为 K 对办公楼(或总计2K个办公楼)安排备份。任一个办公楼都属于唯一的配对组(换句话说,这 2K 
个办公楼一定是相异的)。此外,电信公司需按网络电缆的长度(公里数)收费。因而,你需要选择这 K 对办公
楼使得电缆的总长度尽可能短。换句话说,你需要选择这 K 对办公楼,使得每一对办公楼之间的距离之和(总距
离)尽可能小。下面给出一个示例,假定你有 5 个客户,其办公楼都在一条街上,如下图所示。这 5 个办公楼分
别位于距离大街起点 1km, 3km, 4km, 6km 和 12km 处。电信公司仅为你提供 K=2 条电缆。
[BZOJ2288&BZOJ1150]一类堆+链表+贪心问题
  上例中最好的配对方案是将第 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的某个边界没有元素了(也就是说选到了头),那么我们再反悔的话,会变成这样:
[BZOJ2288&BZOJ1150]一类堆+链表+贪心问题
 
我们发现,如果这时候“反悔”的话,长度不会增加,事实上,任何情况下,选三角都没有选对勾优秀。
因为我在不断贪心,如果选三角优我应该先统计了三角的答案了
比如说1 2 3 4,选了1,显然没有必要把0+2-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给她看了一个神奇的序列 A1A2, ..., AN. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。

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

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

Input

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

第2行, N 个整数 A1A2, ..., AN (0 ≤ |Ai| ≤ 104), 序列。

Output

一个整数,最大的和。

Sample Input

5 2
2 -3 2 -1 2

Sample Output

5
 
题解:
(施工ing。。。。。)