BZOJ4977[Lydsy1708月赛]跳伞求生——贪心+堆+模拟费用流

题目链接：

跳伞求生

可以将题目转化成数轴上有$n$个人和$m$个房子，坐标分别为$a_{i}$和$b_{i}$，每个人可以进一个他左边的房子，每个房子只能进一个人。每个房子有一个收益$c_{i}$，每个人进房子收益为$a_{i}-b_{j}+c_{j}$，不要求所有人都进房子，求最大收益。显然可以建图跑费用流，但数据范围较大，我们考虑模拟费用流。将人和房子放在一起按坐标从小到大排序，相同坐标的按收益(人的收益为$a_{i}$，房子的收益为$c_{i}-b_{i}$)从大到小排序。然后我们用一个大根堆来维护当前能选的房子，按排完序的顺序决策每个点。如果这个点是房子，那么将这个点的收益入堆；如果这个点是人，那么将这个人与堆顶匹配(注意如果这个人与堆顶的收益和小于$0$就不匹配，因为不要求所有人都匹配)并弹出堆顶，因为这个堆顶还有可能和这个点之后的点匹配，所以将这个点的反悔操作插入堆中(即插入$-a_{i}$)，这样如果之后有一个点$j$匹配了$-a_{i}$就表示原本匹配$i$的房子与$j$匹配了。

#include

#include

#include

#include

#include

#include

#define ll long long

using namespace std;

int n,m;

struct lty

{

int x,opt,val;

}a[2000010];

int cnt;

priority_queueq;

ll ans;

bool cmp(lty a,lty b)

{

return a.x==b.x?a.val>b.val:a.x

}

int main()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)

{

cnt++;

scanf("%d",&a[cnt].x);

a[cnt].val=a[cnt].x;

a[cnt].opt=1;

}

for(int i=1;i<=m;i++)

{

cnt++;

scanf("%d%d",&a[cnt].x,&a[cnt].val);

a[cnt].val-=a[cnt].x;

a[cnt].opt=2;

}

sort(a+1,a+1+cnt,cmp);

for(int i=1;i<=cnt;i++)

{

if(a[i].opt==1)

{

if(!q.empty()&&q.top()+a[i].val>0)

{

ans+=q.top()+a[i].val;

q.pop();

q.push(-a[i].val);

}

}

else

{

q.push(a[i].val);

}

}

printf("%lld",ans);

}