1264: yxy和志愿者小姐姐番外篇之大寶寶123追番記

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?時間限制: 1 Sec??內(nèi)存限制: 64 MB
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?提交: 46??解決: 13
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?[提交][狀態(tài)][討論版][命題人:ZBT]

題目描述

yxy和小姐姐幸福而快樂地生活在一起后，就拋棄了他的隊友——大寶寶123

為了填補心靈上的空虛只能無聊地追番（一個番就是一部動漫）

他的計劃是這個月看完M集動漫，他的手頭的錢都給yxy追妹子了，所以他并沒有多少錢，

故而他并不在乎看的是什么番劇，只要不重復地看夠M集(1<=M<=100000)就可以了。
AcmliAcmli動漫網(wǎng)有N個番(1<=N<=100000)，AcmliAcmli動漫網(wǎng)是一個奇特的網(wǎng)站。
它的特點是:
1.收錄的番很獨特，都是無限連載的，也就是說，只要你有錢，從第1集開始你想看多少集就看多少集。
2.收費方式獨特，每部劇都有三個整數(shù)特征值A,B,C(1<=A<=10000,1<=B<=10000,1<=C<=10000),
你看第X集的費用F為:F = A*X^2 + B*X + C
大寶寶123想知道，他追完M集至少需要多少錢

輸入

只有一組數(shù)據(jù)
第一行有兩個整數(shù)，N與M，分別表示AcmliAcmli網(wǎng)站收錄的動漫的個數(shù)和大寶寶123想看的動漫的集數(shù)
接下來M行，每行3個整數(shù)描述一個番的特征值A,B,C

輸出

輸出一個整數(shù)代表大寶寶123同學追完M集至少需要多少錢

樣例輸入

10 5 73 41 47 82 29 78 46 28 18 6 66 67 98 36 85 50 98 27 64 60 95 27 88 62 34 16 39 84 52 1

樣例輸出

618

?

一道充分利用優(yōu)先隊列的題目：算是純模擬吧。

1.將n部劇的第一集存如優(yōu)先隊列中

2.從優(yōu)先隊列中彈出花費最小的一集，一直維護最小的每一集的最小花費

3.將最小集數(shù)花費加入到總的花費中，再將下一集存入優(yōu)先隊列中

4.重復2、3操作，直到看完最后一部劇，輸出結果

?

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<cstring> #include<string>using namespace std; typedef long long LL;struct Node{LL a, b, c;int jishu;LL val;friend bool operator < (const Node& A, const Node& B){return A.val > B.val;} };int n, m; priority_queue<Node>pq;int main() {scanf("%d%d", &n, &m);Node node;for(int i = 0; i < n; i++){scanf("%lld%lld%lld", &node.a, &node.b, &node.c);node.val = node.a + node.b + node.c;node.jishu = 1;pq.push(node);}LL res = 0;for(int i = 0; i < m; i++){res += pq.top().val;node = pq.top();pq.pop();node.jishu++;node.val = node.a*node.jishu*node.jishu + node.b*node.jishu + node.c;pq.push(node);}printf("%lld\n", res);return 0; }

?

總結

以上是生活随笔為你收集整理的yxy和志愿者小姐姐番外篇之大宝宝123追番记（补题，淘汰赛）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。