1.题目

2.题解

2.1 贪心 + 堆

思路

由于如下图公式所示:

1. 要获取的是最大值(最坏情况), 故如果increase增量小于零则没有必要讨论(存在刚开始由于b较大使得增量大于零,而k小于0,后面由于x增大导致增量为负值)
2. 可利用贪心局部最优(每次选择加人时,均是选择增量最大的一组),实现全局最优(最大值)
3. 为了方便每次取最大值,选择使用大根堆自动排序,每次只要取顶部值即可
4. 计算得到每次增量和各个参数的关系: increase = k + b (x=1) / ((x+1)k + b)(x+1) - (xk + b)x = k(2x+1) + b; (x>1)

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
struct Node {
	int k, b, x, increase;
	Node(int k, int b, int x, int increase) : k(k), b(b), x(x), increase(increase){}
	bool operator <(const Node& other) const{
		return increase < other.increase;
	}
};
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n, m;
	cin >> n >> m;
	priority_queue<Node> pq;
	for (int i = 0; i < m; i++){
		Node node(0,0,0,0);
		cin >> node.k >> node.b;
		node.increase = node.k + node.b;
		// 初始化,计算初次所有利润大于 0的(便于第一次选择), 利用大根堆性质增幅最大的放在顶部(贪心,局部最优获取全局最优) 
		if(node.k + node.b > 0){
			node.x = 1;
			pq.push(node);
		}
	}
	
	ll money = 0; 
	for (int person = 0; person < n && !pq.empty(); person++){
		Node node = pq.top();
		pq.pop();
		money += node.increase;
		// 下一次的增幅, ((x+1)*k + b)(x+1) - (x*k + b)x = k(2x+1) + b;  
		node.increase =  (2*node.x + 1) * node.k + node.b;
		if(node.increase > 0){
			node.x += 1;
			pq.push(node);
		} 
	}
	
	cout << money;
	return 0; 
}