1 条题解

  • 0
    @ 2026-10-13 16:16:17

    赛时观察到性质了,但是为了少写一行排序还是多加了一个反贪策略,果不其然被反噬了,导致我想复杂了,其实一点都到不了紫

    设订单为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
    上传者