欢迎访问~原文出处——
题意
小明组建了一支由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#include #include #include #include #include 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 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;}