思路讲解
主要思路就是使用二叉堆的一个贪心（pq）
把这个障碍物前面的全部奖励都放到pq里，然后用一个弹出一个，避免后面重复用，还有一个就是降低算法复杂度
其实还有一个对于算法复杂度的一个判断
其实push pq不用担心时间复杂度的问题，因为用过的我们都会push掉，所以每个奖励我们只会遍历一次，所以差不多是O(nlogn+mlogm)
AC代码
https://codeforces.com/contest/2037/submission/293963686
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T,m,L;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while (T--) {
cin>>n>>m>>L;
vector<pair<ll,ll> > ban(n+5),enc(m+5);
vector<ll> senc(m+5,0);
priority_queue<ll> q;
for(int i=1;i<=n;++i){
cin>>ban[i].first>>ban[i].second;
}
for(int i=1;i<=m;++i){
cin>>enc[i].first>>enc[i].second;
}
for(int i=1;i<=m;++i)
senc[i]=senc[i-1]+enc[i].second;
ll sadd=1;
ll curk=1;
ll ans=0;
bool isBreak=false;
for(int i=1;i<=n;++i){
ll len=ban[i].second-ban[i].first+1;
if(curk>len){
continue;
}
ll idx=lower_bound(enc.begin() + 1, enc.begin() + m + 1,make_pair(ban[i].first,0LL))-enc.begin()-1;
if(senc[idx]+1<=len){
cout<<-1<<endl;
isBreak=true;
break;
}
for(int i=sadd;i<=idx;++i){
q.push(enc[i].second);
}
while(!q.empty()){
curk+=q.top();
q.pop();
++ans;
if(curk>len)
break;
}
sadd=idx+1;
}
if(!isBreak)
cout<<ans<<endl;
}
return 0;
}
|
心路历程（WA，TLE，MLE……）
二分搜索vector记得这么写
1
| ll idx=lower_bound(enc.begin() + 1, enc.begin() + m + 1,make_pair(ban[i].first,0LL))-enc.begin()-1;
|