题解：CF1218F Workout plan

思路

很好看出这是一道贪心的题目。

贪心策略

如果某一天的力量不足，那就必须要在之前购买一些饮料。
饮料可以在任何天购买，而且价格不同。为了尽可能使花费更小，所以应该在价格较低的健身房购买饮料。

实现

使用一个最小堆（优先队列）来维护所有健身房的饮料价格（包括当前天）。

遍历每一天：

将当天健身房的饮料价格加入最小堆。
若当前力量 $<x_i$ ，则从堆中价格最小的健身房买一瓶饮料，然后弹出堆里，直到力量 $\ge x_i$ ，若堆为空，就直接输出 $-1$ 。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long

main(){
    int n,k;
	cin>>n>>k;
    vector<int>x(n);
	for(int i=0;i<n;i++) cin>>x[i];
	int m;
	cin>>m;
	vector<int>c(n);
	for(int i=0;i<n;i++) cin>>c[i];
    int cur=k,cost=0;
	priority_queue<int,vector<int>,greater<int>>pq;//用优先队列是因为它可以自动把花费最小的元素放在堆顶
	for(int i=0;i<n;i++){
		pq.push(c[i]);
		while(cur<x[i]){//如果能量不够，就要买饮料知道够为止
			if(!pq.size()){//如果都买完了，就输出-1
				cout<<-1;
				return 0;
			}
			cost+=pq.top();
			pq.pop();//弹出指的是这个健身房的饮料已经买了，就不能再买了
			cur+=m;
		}
	}
	cout<<cost;
	return 0;
}

题解：CF1218F Workout plan

文章操作

思路

贪心策略

实现

代码

相关推荐

评论

题解：CF1218F Workout plan