2023-08-10：景区里有 m 个项目，也就是项目数组为 int[][] game，这是一个 m*2 的二维数组
景区的第 i 个项目有如下两个参数：
game[i] = { Ki, Bi }
Ki 一定是负数，Bi 一定是正数
举个例子 :
Ki = -2, Bi = 10
如果只有 1 个人买票，单张门票的价格为 : Ki * 1 + Bi = 8
所以这 1 个人游玩该项目要花 8 元
如果有 2 个人买票，单张门票的价格为 : Ki * 2 + Bi = 6
所以这 2 个人游玩该项目要花 6 * 2 = 12 元
如果有 5 个人买票，单张门票的价格为 : Ki * 2 + Bi = 0
所以这 5 个人游玩该项目要花 0 * 5 = 0 元
如果有更多人买票，都认为花 0 元(因为你让项目倒贴钱实在是太操蛋了)
于是可以认为，如果有 x 个人买票，单张门票的价格为 : Ki * x + Bi
x 个人游玩这个项目的总花费是 : max { (Ki * x + Bi) * x , 0 }
你作为领导，单位一共有 n 个人，每个人最多可以选 1 个项目来游玩，也可以不选任何项目
所有员工将在明晚提交选择，然后由你去按照上面的规则，统一花钱，统一购票
但是现在，你想知道自己需要准备多少钱，就可以应付可能的各种情况，
支持各种可能下的开销，返回这个最保险的钱数。
数据量描述 :
1 <= N、M、Bi <= 10^5，
-(10^5) <= Ki < 0。
来自左程云。
答案 2023-08-10：
步骤描述：
1.创建一个优先队列（堆）h，用于存储游戏项目。我们使用 GameHeap 类型来定义优先队列，并实现 Len、Less、Swap、Push 和 Pop 方法。
2.遍历每个项目 g，在遍历过程中将 Ki 和 Bi 作为参数创建 Game 结构体 game，并将其添加到优先队列 h 中。
3.初始化结果变量 ans 为 0，用于记录总花费。
4.迭代 n 次，表示有 n 个人进行选择游戏项目的操作。
4.1.检查当前优先队列 h 的第一个项目的 Earn 值（单张门票的价格乘以人数）。如果 Earn 值小于等于 0，即项目不再划算，跳出循环。
4.2.从优先队列 h 中弹出一个项目，并将其赋值给变量 cur。
4.3.将当前项目的 Earn 值累加到结果变量 ans 中。
4.4.增加当前项目的人数 cur.People。
4.5.将更新后的项目 cur 添加回优先队列 h 中。
5.返回结果变量 ans，即准备的最保险的金额。
总的时间复杂度：O(nlog(m))，其中 n 为人数，m 为项目数。遍历 n 次，每次从优先队列中弹出最大值，时间复杂度为 log(m)。
总的空间复杂度：O(m)，优先队列 h 的大小取决于项目数 m。
go 完整代码如下：
package main
import ( "container/heap" "fmt")
type Game struct { Ki int Bi int People int}
type GameHeap []Game
func (h GameHeap) Len() int { return len(h) }func (h GameHeap) Less(i, j int) bool { return h[i].Earn() > h[j].Earn() }func (h GameHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }func (h *GameHeap) Push(x interface{}) { *h = append(*h, x.(Game)) }func (h *GameHeap) Pop() interface{} { old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x}
func (g Game) Earn() int { return (2*g.People+1)*g.Ki + g.Bi}
func EnoughMoney(n int, games [][]int) int { h := &GameHeap{} heap.Init(h)
for _, g := range games { game := Game{Ki: g[0], Bi: g[1]} heap.Push(h, game) }
ans := 0 for i := 0; i < n; i++ { if (*h)[0].Earn() <= 0 { break } cur := heap.Pop(h).(Game) ans += cur.Earn() cur.People++ heap.Push(h, cur) }
return ans}
func main() { games := [][]int{{-2, 10}, {-1, 5}, {-3, 15}} n := 5 result := EnoughMoney(n, games) fmt.Println(result)}
复制代码
c++完整代码如下：
#include <iostream>#include <queue>#include <vector>using namespace std;
struct Game { int Ki; int Bi; int people;
Game(int k, int b) { Ki = k; Bi = b; people = 0; }
int earn() const { return (2 * people + 1) * Ki + Bi; }};
struct CompareGame { bool operator()(const Game& a, const Game& b) { return a.earn() < b.earn(); }};
int enoughMoney(int n, vector<vector<int>>& games) { priority_queue<Game, vector<Game>, CompareGame> heap;
for (auto& g : games) { heap.push(Game(g[0], g[1])); }
int ans = 0;
while (n > 0 && heap.top().earn() > 0) { Game cur = heap.top(); heap.pop();
ans += cur.earn(); cur.people++; heap.push(cur);
n--; }
return ans;}
int main() { vector<vector<int>> games = { {-2, 10}, {-1, 5}, {-3, 15} }; int n = 5;
int result = enoughMoney(n, games); cout << "Amount needed: " << result << endl;
return 0;}
复制代码
c 语言完整代码如下：
#include <stdio.h>#include <stdlib.h>
struct Game { int Ki; int Bi; int people;};
typedef struct Game Game;
int cmp(const void* a, const void* b) { Game* gameA = (Game*)a; Game* gameB = (Game*)b; return (2 * gameB->people + 1) * gameB->Ki + gameB->Bi - (2 * gameA->people + 1) * gameA->Ki - gameA->Bi;}
int enoughMoney(int n, int games[][2], int m) { Game* heap = (Game*)malloc(m * sizeof(Game)); for (int i = 0; i < m; i++) { heap[i].Ki = games[i][0]; heap[i].Bi = games[i][1]; heap[i].people = 0; }
qsort(heap, m, sizeof(Game), cmp);
int ans = 0;
for (int i = 0; i < n; i++) { if ((2 * heap[0].people + 1) * heap[0].Ki + heap[0].Bi <= 0) { break; } ans += (2 * heap[0].people + 1) * heap[0].Ki + heap[0].Bi; heap[0].people++; qsort(heap, m, sizeof(Game), cmp); }
free(heap);
return ans;}
int main() { int games[][2] = { {-2, 10}, {-1, 5}, {-3, 15} }; int n = 5; int m = sizeof(games) / sizeof(games[0]);
int result = enoughMoney(n, games, m); printf("Total money needed: %d\n", result);
return 0;}
复制代码
![2023-08-10：景区里有m个项目，也就是项目数组为int[][] game，这是一个m*2的二维数组 景区的第i个项目有如下两个参数： game[i] = { Ki, Bi } Ki一定是负数，_左程云_福大大架构师每日一题_InfoQ写作社区](https://static001.infoq.cn/static/infoq/img/logo-121-75.yuij86g.png){kind=logo}
评论