本文介绍: 2、可以用优先队列存项目的k、b、x(选择这个项目的人数)、increase（当前项目人数增加为x+1所增加的花费），使increase最大的项目排在队首，每加一个人出队一个并使总花费增加increase，即总花费money = money + increase。1、每个人依此选择项目，每个人选项目时都（选择当下花费增加最多的项目），若项目i的门票价格为kx+b，那么增加一个人选择的花费为：increase =(k*(x+1)+b)*（x+1）- ((k*x)+b)*x x = k(2x+1) + b。
优先队列： 蓝桥杯（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);
}
}
else
break;
}
cout << money;
}
原文地址:https://blog.csdn.net/qq_74156152/article/details/135699616
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_60514.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
