D2T2 跳伞求生
传送门
Description：
小Q最近沉迷于《跳伞求生》游戏。他组建了一支由 $n$ 名玩家（包括他自己）组成的战队，编号依次为$1,2,\dots,n$ 。这个游 戏中，每局游戏开始时，所有玩家都会从飞机上跳伞，选择一个目的地降落，跳伞和降落的时间有早有晚。在某局 游戏降落前，他们在空中观察发现地面上一共有 $m$ 间房子，编号依次为 $1$ 到 $m$ 。其中每间房子恰好有一名敌人早于他 们到达。小Q战队的第 $i$ 名玩家拥有 $a_i$发子弹，地面上第i间房子里的敌人拥有 $b_i$ 发子弹，消灭他可以获得 $c_i$ 点积 分。每名玩家必须且只能选择一间房子降落，然后去消灭里面的敌人。若第i名玩家选择了第j间房子，如果 $a_i>b_ j$ ，那么他就可以消灭该敌人，获得 $a_i-b_j+c_j$ 的团队奖励积分，否则他会被敌人消灭。为了防止团灭，小Q不允 许多名玩家选择同一间房子，因此如果某位玩家毫无利用价值，你可以选择让他退出游戏。因为房子之间的距离过长，你可以认为每名玩家在降落之后不能再去消灭其它房间里的敌人。作为小Q战队的指挥，请制定一套最优的降 落方案，使得最后获得的团队奖励总积分最大
Solution：
对于人的贡献为 $a_i$ ，房子的贡献为 $c_j-b_j$ 。 将 $c_j-b_j$ 从大到小排序。对于贡献大的房子，也要用 $a_i$ 大的取消除。用一个 $multiset$ 维护 $a$ ，如果有能消灭敌人的人，并更新答案。
Code:
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
40
41
42
43
44
45
46
47
48
49
| #include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
#define in read()
#define ll long long
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*f;
}
struct room{
int b,c,val;
}p[maxn];
int n,m,a[maxn];
multiset<int> s;
bool cmp1(int a,int b){
return a>b;
}
bool cmp2(room a,room b){
return a.val>b.val;
}
int main(){
n=in;m=in;
for(int i=1;i<=n;i++) a[i]=in,s.insert(a[i]);
for(int i=1;i<=m;i++){
p[i].b=in;p[i].c=in;
p[i].val=p[i].c-p[i].b;
}
sort(a+1,a+1+n,cmp1);
sort(p+1,p+1+m,cmp2);
ll ans=0,tot=0;
int cnt=0;
for(int i=1;i<=m;i++){
multiset<int>::iterator it=s.lower_bound(p[i].b+1);
if(it!=s.end()){
ans=max(ans,tot+=a[++cnt]+p[i].val);
s.erase(it);
}
}
printf("%lld\n",ans);
return 0;
}
|
诶难道不是线段树专题吗？因为这道题还可以用线段树模拟费用流来做
