本文主要是介绍蓝桥杯（C++ 最大开支 优先队列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
优先队列： 蓝桥杯（C++ 整数删除 优先队列 ）-CSDN博客
思路：
1、每个人依此选择项目，每个人选项目时都（选择当下花费增加最多的项目），若项目i的门票价格为kx+b，那么增加一个人选择的花费为：increase =(k*(x+1)+b)*（x+1）- ((k*x)+b)*x x = k(2x+1) + b
2、可以用优先队列存项目的k、b、x(选择这个项目的人数)、increase（当前项目人数增加为x+1所增加的花费），使increase最大的项目排在队首，每加一个人出队一个并使总花费增加increase，即总花费money = money + increase
3、更新x和increase，若increase > 0重新入队，若increase <= 0不重新入队(人数到了开口向下的二次函数的对称轴，花费开始下降，不能再增加人数了
代码：
#include<iostream>
#include<queue>
#include<functional>
using namespace std;
using ll = long long;
struct node
{int k, b, x , increase;
};
bool operator < (const struct node a, const struct node b)//重载<
{return a.increase < b.increase;
}
int main()
{int n, m;cin >> n >> m;priority_queue<node>h;//大根堆node a;for (int i = 0; i < m; i++){cin >> a.k >> a.b;a.increase = a.k + a.b;if (a.increase <= 0)//小于等于零的不入队continue;a.x = 1;h.push(a);}ll money = 0, person;for (person = 0; !h.empty() && person < n; person++){if (h.top().increase > 0)//防止第一个就小于零{node temp = h.top();h.pop();money += temp.increase;//加上增加的花费//increase=(k*(x+1)+b)*（x+1）-((k*x)+b)*x 再增加一个人会不会比之前花费更多temp.increase = temp.k * (2 * temp.x + 1) + temp.b;if (temp.increase > 0)//比之前还更多，重新入队{temp.x += 1;h.push(temp);}}elsebreak;}cout << money;
}
这篇关于蓝桥杯（C++ 最大开支 优先队列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
