1 条题解
-
0
赛时观察到性质了,但是为了少写一行排序还是多加了一个反贪策略,果不其然被反噬了,导致我想复杂了,其实一点都到不了紫
设订单为p,房间为h,价值(收益和花费)为val,人数为w,如下:(另外,限制O为K)
struct node{ int val,w; }h[500005],p[500005];Part1
首先看到重要性质:pi < pj , 则 ci <= cj (单调性非常明显)
那么一个订单 优先选用 能装下它的空间最小的 花费最小的 房间
当然,最优的房间可能已被占了,那就选下一个,但这样可能占用后面的订单的房间
我们并不能保证这是最优的,因为单调性是属于 h 而非 p 的
那我们可以考虑 枚举 h 选 p
Part2
那么我们先对 h 进行排序( p 也排),如下:
bool operator <(const node t)const{ if(w==t.w) return val<t.val;//其实订单不需要这一行 return w<t.w; }那么我们遍历房间,开一个priority_queue表示可以使用但没使用的 p,每次从里面拿出val最大的,尝试计入答案
Part3
但这样也不一定最优,因为我们没有考虑 限制K
当选满 K 个时,如果有新的一对,产生的价值 > 某个已选过的 时,要更新
所以要新建一个priority_queue装已选过的对产生的价值
当选满时,取最小的那个与当前的那个 尝试更新
Code
#include<bits/stdc++.h> using namespace std; struct node{ int val,w; bool operator <(const node t)const{ if(w==t.w) return val<t.val; return w<t.w; } }h[500005],p[500005]; const int INF=2e9; int n,m,K;long long ans; int main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m>>K; for(int i=1;i<=n;i++){ cin>>h[i].val>>h[i].w; } for(int i=1;i<=m;i++){ cin>>p[i].val>>p[i].w; } sort(h+1,h+n+1); sort(p+1,p+m+1); priority_queue<int> q,Q;//q:可使用但未使用的p,Q:已计入的价值 q.push(0);Q.push(-INF);//这样就不用判空了 for(int i=1,j=0,k=0;i<=n;i++){ while(j<m&&p[j+1].w<=h[i].w) q.push(p[++j].val); int a=q.top(),b=Q.top(),c=h[i].val; b=-b; if(k<K){ if(a>c) ans+=a-c,q.pop(),Q.push(c-a),k++; } else if(a-c>b){ ans+=a-c-b; q.pop(),Q.pop(); Q.push(c-a); } } cout<<ans; return 0; }目前在洛谷是第三优解
- 1
信息
- ID
- 899
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 60
- 已通过
- 8
- 上传者