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);
}