“请告诉我为何心不停的跳动 这颗心究竟装着什么” —— 《人偶之梦》
分析
注意到 pi<pj 则 ci≤cj，存在偏序关系。
一个贪心的想法是，按照订单的 v 从大到小，每次找到大于 d 的最小的 p 住进去。
但是如果房间已经被占用，就住进大于 d 的 p 最小的没有被占用的房间，而不是把占用清除。
考虑这样为什么是对的，设占用房间的为 i，要住进去的为 j。
- 如果 i,j 都要入住，答案无影响。
- 如果 i,j 只有一个要入住，因为 vi>vj，所以 i 肯定比 j 更优，j 必定不会被选到（就选选的不是最优的房间也不影响）。
现在问题变成了，找到大于 d 的 p 最小的没有被占用的房间，然后把这个房间删除，multiset 可以解决（注意房间可重，set 不可重）。
代码
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
| multiset<pair<int,int>> house;
vector<pair<int,int>> order;
int n,m,o;
int main(){
n = in(),m = in(),o = in();
for(int k=1;k<=n;k++){
int c = in(),p = in();
house.insert({p,c});
}
order.resize(m);
for(auto &[v,d]:order)
v = in(),d = in();
sort(order.begin(),order.end(),[](auto a,auto b){return a.first!=b.first?a.first>b.first:a.second<b.second;});
vector<int> res;
for(auto [v,d]:order){
auto it = house.lower_bound({d,0});
if(it!=house.end()){
if(v<=(*it).second)
continue;
res.push_back(v-(*it).second);
house.erase(it);
}
}
sort(res.begin(),res.end(),greater<>());
long long ans = 0;
for(int k=0;k<min(o,(int)res.size());k++)
ans += res[k];
out(ans);
return 0;
}
|
闲话
pi<pj 则 ci≤cj 放在题面更合理吧，放在数据范围有点抽象。