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 mainimport (    "container/heap"    "fmt")type Game struct {    Ki     int    Bi     int    People int}type GameHeap []Gamefunc (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;}

在这里插入图片描述

福大大架构师每日一题java当死，golang当立。最新面试题，涉及golang，rust，mysql，redis，云原生，算法，分布式，网络，操作系统。621篇原创内容

公众号

福大大架构师每日一题，赞6