JZOJ 5271.神奇的救火现场

第一次见可撤销贪心,还是个可以线性做的假标算(

首先大概讲一下线性做法。
排个序,注意到消防站和水栓的匹配没有交一定不会劣于最优解。
考虑顺序逆序各匹配一遍,分别找最近的没被匹配的。
将匹配连边。
于是将已经确定的匹配的贡献计算,然后没有确定的匹配一定是多出一个水栓,枚举去掉的水栓取最小值即可。

这个做法有点难写,所以我写了标算的可撤销贪心(

依然排个序,去掉绝对值。将每个坐标的相反数插入堆中,然后每次取出堆顶。
但是要支持撤销,那么就在堆中插入时计入撤销本次操作的贡献。
然后注意区分水栓和消防站。
具体可见代码。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5;
int n,m;
struct note
{
int op,x;
inline bool operator<(const note &o) const
{
return x < o.x;
}
} a[(N << 1) + 5];
priority_queue< int,vector<int>,greater<int> > q[2];
long long ans;
int main()
{
freopen("fire.in","r",stdin),freopen("fire.out","w",stdout);
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;++i)
scanf("%d",&a[i].x);
for(register int i = 1;i <= m;++i)
scanf("%d",&a[i + n].x),a[i + n].op = 1;
n += m;
sort(a + 1,a + n + 1);
for(register int i = 1;i <= n;++i)
{
if(q[a[i].op ^ 1].empty())
{
a[i].op ? (ans += 0x3f3f3f3f,q[1].push(-a[i].x - 0x3f3f3f3f)) : q[0].push(-a[i].x);
continue;
}
int v = a[i].x + q[a[i].op ^ 1].top();
(a[i].op || v < 0) && (q[a[i].op ^ 1].pop(),ans += v,q[a[i].op].push(-a[i].x - v),1);
!a[i].op && v >= 0 && (q[a[i].op].push(-a[i].x),1);
}
printf("%lld\n",ans);
}