题解：CF1218F Workout plan

Yang_Jun · 2025-08-25 19:11:49 · 题解

思路

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

贪心策略

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

实现

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

遍历每一天：

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

代码

#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;
}