D. A Game with Traps
题意
有m个士兵每个士兵有属性值ai
k个陷阱每个陷阱分布在1到n上
每个陷阱(陷阱位置在li)有一个属性值di和一个接触此陷阱的开关在ri位置 注意 ri>=li
你需要在t时间内将尽量多的士兵从0带到n+1
你可以解除陷阱，由士兵组成的队伍不能通过某个陷阱当且仅当陷阱的属性值大于队伍中某一士兵的属性值
二分挑出能力最大的mid个士兵筛选有威胁的陷阱
对于当前前面有炸弹时，我们要考虑拆这个炸弹，拆完之后是继续往后拆，还是直接回去。
这个我们画图就能知道，如果两个炸弹起点和终点位置有交叉，那么就继续拆，否则直接回去。
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
| # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int sold[(int)2e5+5];
int m,n,k,t;
struct Data{
int l,r,d;
}trap[(int)2e5+5];
int cnt[(int)2e5+5];
bool cmp(int a,int b){return a>b;}
bool check(int mid){
int minn=mid!=0?sold[mid-1]:(int)2e5+5;
memset(cnt,0,sizeof cnt);int sum=0;
for(int i=0;i<k;i++){
if(trap[i].d<=minn)continue;
cnt[trap[i].l]++;
cnt[trap[i].r+1]--;
}
for(int i=1;i<=n+1;i++)cnt[i]+=cnt[i-1];
for(int i=1;i<=n+1;i++)sum+=(cnt[i]>=1);
return sum*2+n+1<=t;
}
int main(){
std::ios::sync_with_stdio(false);
cin>>m>>n>>k>>t;
for(int i=0;i<m;i++)cin>>sold[i];
for(int i=0;i<k;i++){
cin>>trap[i].l>>trap[i].r>>trap[i].d;
}
sort(sold,sold+m,cmp);
int L=0,R=m,ans=0;
while(L<R){
int mid=(L+R+1)>>1;
if(check(mid)){
ans=mid;
L=mid;
}
else R=mid-1;
}
cout<<ans<<endl;
}
|