【Codeforces】1219D - Workout plan

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/weixin_42449444/article/details/101836032

Problem Description：

Alan decided to get in shape for the summer, so he created a precise workout plan to follow. His plan is to go to a different gym every day during the next N days and lift X[i] grams on day i. In order to improve his workout performance at the gym, he can buy exactly one pre-workout drink at the gym he is currently in and it will improve his performance by A grams permanently and immediately. In different gyms these pre-workout drinks can cost different amounts C[i] because of the taste and the gym's location but its permanent workout gains are the same. Before the first day of starting his workout plan, Alan knows he can lift a maximum of K grams. Help Alan spend a minimum total amount of money in order to reach his workout plan. If there is no way for him to complete his workout plan successfully output -1.

Input Specification:

The first one contains two integer numbers, integers N (1≤N≤

10^{5}

) and K (1≤K≤

10^{5}

)– representing number of days in the workout plan and how many grams he can lift before starting his workout plan respectively. The second line contains N integer numbers X[i] (1≤X[i]≤

10^{9}

) separated by a single space representing how many grams Alan wants to lift on day i. The third line contains one integer number A (1≤A[i]≤

10^{9}

) representing permanent performance gains from a single drink. The last line contains N integer numbers C[i] (1≤C[i]≤

10^{9}

, representing cost of performance booster drink in the gym he visits on day i.

Output Specification:

One integer number representing minimal money spent to finish his workout plan. If he cannot finish his workout plan, output -1.

Sample Input1:

5 10000 10000 30000 30000 40000 20000 20000 5 2 8 3 6

Sample Output1:

5

Sample Input2:

5 10000 10000 40000 30000 30000 20000 10000 5 2 8 3 6

Sample Output2:

-1

Note:

First example: After buying drinks on days 2 and 4 Alan can finish his workout plan. Second example: Alan cannot lift 40000 grams on day 2.

解题思路：

题目大意是Alan最开始能举重K，希望在N天里每天都能完成X[i]的举重量任务，健身房的饮料每天的价格是C[i]，每瓶饮料能让Alan增加A的举重量，求Alan在能保证完成每天的举重任务的前提下，最少花费是多少，若不能完成举重任务输出-1。这题是在请教了Aaver苗神之后才AC的，可以采用一个升序排列的优先队列priority_queue来对问题进行求解。先把当天的饮料价格C[i]推入优先队列中，若当天能完成举重任务，那没事了；若当天不能完成举重任务，就将优先队列中队首的饮料价格累加到sum，使用了钞能力之后的Alan举重能力就能在K的基础上提升A，一直使用钞能力直到Alan能完成当天的任务为止。要是队列空了还是不能完成当天的任务就说明Alan的钞能力并不管用，直接输出-1。否则输出Alan买饮料的总费用sum。

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long ll;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n,k;
    cin >> n >> k;
    int w[n+1];
    ms(w,0);
    Up(i,1,n)
    {
        cin >> w[i];
    }
    int a;
    cin >> a;
    int c[n+1];
    Up(i,1,n)
    ms(c,0);
    Up(i,1,n)
    {
        cin >> c[i];
    }
    ll sum = 0;
    priority_queue<int,vector<int>,greater<int> > pq;   //升序排列的优先队列
    Up(i,1,n)
    {
        pq.push(c[i]);
        while(k < w[i])
        {
            if(pq.empty())
            {
                cout << -1 << endl;
                return 0;
            }
            sum += pq.top();
            pq.pop();
            k += a;
        }
    }
    cout << sum << endl;
    return 0;
}