2023-08-10：景區(qū)里有m個項目，也就是項目數(shù)組為int[][] game，這是一個m*2的二維數(shù)組
2023-08-10：景區(qū)里有m個項目，也就是項目數(shù)組為int[][] game，這是一個m*2的二維數(shù)組
景區(qū)的第i個項目有如下兩個參數(shù)：
game[i] = { Ki, Bi }
Ki一定是負(fù)數(shù)，Bi一定是正數(shù)
舉個例子 :
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元
如果有更多人買票，都認(rèn)為花0元(因為你讓項目倒貼錢實在是太操蛋了)
于是可以認(rèn)為，如果有x個人買票，單張門票的價格為 : Ki * x + Bi
x個人游玩這個項目的總花費(fèi)是 : max { (Ki * x + Bi) * x , 0 }
你作為領(lǐng)導(dǎo)，單位一共有n個人，每個人最多可以選1個項目來游玩，也可以不選任何項目
所有員工將在明晚提交選擇，然后由你去按照上面的規(guī)則，統(tǒng)一花錢，統(tǒng)一購票
但是現(xiàn)在，你想知道自己需要準(zhǔn)備多少錢，就可以應(yīng)付可能的各種情況，
支持各種可能下的開銷，返回這個最保險的錢數(shù)。
數(shù)據(jù)量描述 :
1 <= N、M、Bi <= 10^5，
-(10^5) <= Ki < 0。
來自左程云。
答案2023-08-10：
步驟描述：
1.創(chuàng)建一個優(yōu)先隊列（堆）h，用于存儲游戲項目。我們使用GameHeap類型來定義優(yōu)先隊列，并實現(xiàn)Len、Less、Swap、Push和Pop方法。
2.遍歷每個項目g，在遍歷過程中將Ki和Bi作為參數(shù)創(chuàng)建Game結(jié)構(gòu)體game，并將其添加到優(yōu)先隊列h中。
3.初始化結(jié)果變量ans為0，用于記錄總花費(fèi)。
4.迭代n次，表示有n個人進(jìn)行選擇游戲項目的操作。
4.1.檢查當(dāng)前優(yōu)先隊列h的第一個項目的Earn值（單張門票的價格乘以人數(shù)）。如果Earn值小于等于0，即項目不再劃算，跳出循環(huán)。
4.2.從優(yōu)先隊列h中彈出一個項目，并將其賦值給變量cur。
4.3.將當(dāng)前項目的Earn值累加到結(jié)果變量ans中。
4.4.增加當(dāng)前項目的人數(shù)cur.People。
4.5.將更新后的項目cur添加回優(yōu)先隊列h中。
5.返回結(jié)果變量ans，即準(zhǔn)備的最保險的金額。
總的時間復(fù)雜度：O(nlog(m))，其中n為人數(shù)，m為項目數(shù)。遍歷n次，每次從優(yōu)先隊列中彈出最大值，時間復(fù)雜度為log(m)。
總的空間復(fù)雜度：O(m)，優(yōu)先隊列h的大小取決于項目數(shù)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++完整代碼如下：
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語言完整代碼如下：
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;
}
