BZOJ4977 八月月赛 Problem G 跳伞求生 set 贪心

时间:2024-09-08 13:37:08

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解


题目传送门 - BZOJ4977 - 八月月赛 Problem G


题意

  小明组建了一支由n名玩家组成的战队,编号依次为1到n。每局游戏开始时,所有玩家都会从飞机上跳伞,选择一个目的地降落。他们发现地面上一共有m间房子,编号依次为1到m。每间房子有一名敌人。第i名玩家有ai发子弹,第i间房子里的敌人有bi发子弹,消灭他可以获得ci点积分。每名玩家必须且只能选择一间房子降落。若第i名玩家选择了第j间房子,如果ai>bj,他就可以消灭该敌人,获得ai-bj+cj的积分。如果某位玩家无价值,你可以让他退出。每名玩家在降落之后不能再去消灭其它房间里的敌人。请制定一套最优的降落方案,使得最后获得的总积分最大。输出这个最大值。

题解

  玩家的子弹是一定的。
  一个房子的贡献也是一定的,那么就是ci-bi。
  那么我们贪心的尽量让我们的玩家选择贡献大的房子。
  所以我们先按照房子的贡献排序。
  然后依次选择下去,用一个set维护ai。对于一个房子,我们要选择能剩余未选择的玩家中能打下它的尽量小的,所以upper_bound。
  与此同时,我们统计出可以打下的房子个数tot以及这些房子各自的贡献值v。
  如果我们要选择一些人来打房子,那么一定会选择最大的。
  于是我们把ai降序排序,然后用前tot个来打。
  打的时候还是有讲究的。
  我们已经确定了贡献值序列v和a序列,各有tot个元素。
  我们都给他们升序排序。
  这个a序列一定是有办法打下所有的v的。
  但是,如果不打下所有的v,有可能会更赚。
  对于排好序的a[i]和v[i],如果a[i]+v[i]<0,那么还是不打这个房子v[i]了。
  亏的。
  那么,我们可以稍微的改动一下。
  因为a[i]和v[i]都是排好序的,所以其实就是前面的一段不打了。
  为什么不打?假如可以打掉,也是亏的。
  我们考虑打tot组的方案,那么总价值是一定的。
  而对于tot组去掉一组的情况,那么更改的总价值也是一定的。
  是什么呢,就是在人中踢去一个最弱的,在v[i]中也踢去一个最没用的。
  那么之后的tot-1组一定可以保证可以每个都打掉。为什么?回忆之前的打法。
  那么,这tot组和tot-1组的总价值差是什么呢,就是扔掉的人和房子的a[i]+v[i]。
  所以,我们从小到大,依次尝试扔掉人和房子,直到人和房子的价值和不再是负的位置。

代码

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
using namespace std;
typedef long long LL;
const int N=100000+5;
int n,m,a[N],v[N],tt[N];
struct House{
int b,c,v;
bool operator < (const House x) const{
if (v==x.v)
return b>x.b;
return v>x.v;
}
}h[N];
set <int> p;
bool cmp_BigFirst(int a,int b){
return a>b;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1,cmp_BigFirst);
for (int i=1;i<=m;i++){
scanf("%d%d",&h[i].b,&h[i].c);
h[i].v=h[i].c-h[i].b;
}
memset(tt,0,sizeof tt);
p.clear();
for (int i=1;i<=n;i++){
p.insert(a[i]);
tt[a[i]]++;
}
int tot=0;
sort(h+1,h+m+1);
for (int i=1;i<=m;i++){
if (p.upper_bound(h[i].b)==p.end())
continue;
int now=*p.upper_bound(h[i].b);
tt[now]--;
if (!tt[now])
p.erase(now);
v[++tot]=h[i].v;
}
LL ans=0;
sort(v+1,v+tot+1);
sort(a+1,a+tot+1);
for (int i=1;i<=tot;i++)
if (a[i]+v[i]>0)
ans+=a[i]+v[i];
printf("%lld",ans);
return 0;
}