傳送門

?參考資料

　2019CCPC網(wǎng)絡(luò)選拔賽 H.Fishing Master(思維+貪心)

?題意

　　池塘里有 n 條魚(yú)，捕捉一條魚(yú)需要花費(fèi)固定的 k 時(shí)間；

　　你有一個(gè)鍋，每次只能煮一條魚(yú)，其中煮熟第 i 條魚(yú)至少需要 t_i?時(shí)間；

　　你在煮魚(yú)的時(shí)候可以選擇去釣一條魚(yú)，也可也選擇不釣；

　　但是，一旦你決定釣魚(yú)，就必須花費(fèi) k 時(shí)間調(diào)到一條魚(yú)；

　　任何時(shí)刻，你都可以有多條魚(yú)待煮；

　　問(wèn)將所有的魚(yú)釣上來(lái)并煮熟所有的魚(yú)最少需要多少時(shí)間；

?題解

　　理想的方案是只有在釣第一條魚(yú)的時(shí)候鍋是空的，其余任意時(shí)刻，鍋都在做有用功；

　　鍋在做有用功指的是第 i 條魚(yú)在鍋中煮的前 t_i?時(shí)間，多煮的時(shí)間稱鍋在做無(wú)用功；

　　這種情況下，只需要且必須花費(fèi)?$k+\sum_{i=1}^{n}t_i$ 時(shí)間就可以將所有魚(yú)全部釣上來(lái)并全部煮好；

　　那么，實(shí)際情況并非如此，要想花費(fèi)最少的時(shí)間，首先得明確在什么情況下可能會(huì)導(dǎo)致時(shí)間浪費(fèi)；

　　假設(shè)你當(dāng)前煮的魚(yú)需要花費(fèi) t 時(shí)間，釣魚(yú)需要花費(fèi) k 時(shí)間；

　　你可以在這 t 時(shí)間內(nèi)釣 $\frac{t}{k}$?條魚(yú)上來(lái)，在釣魚(yú)的時(shí)間，鍋處于煮魚(yú)狀態(tài)；

　　但是剩下的 t%k 時(shí)間不足以再釣一條上來(lái)；

　　此時(shí)，你就有兩個(gè)決策可以選擇：

　　　　決策1：去釣下一條魚(yú)；

　　　　決策2：等待 t%k 時(shí)間往鍋中放入下一條魚(yú)；

　　當(dāng)然，選擇 決策2 的前題是你得有魚(yú)可煮；

　　如果你手中有魚(yú)的話，肯定要選擇 決策2，因?yàn)榈却倪@ t%k 時(shí)間是必須的；

　　而如果選擇 決策1，那么煮當(dāng)前這條魚(yú)會(huì)花費(fèi) t+k-t%k 時(shí)間，前 t 時(shí)間鍋在做有用功，是必須的；

　　但是后 k-t%k 時(shí)間，鍋就在做無(wú)用功，是在浪費(fèi)時(shí)間；

　　如果你當(dāng)前手中無(wú)魚(yú)，那么你不得不去釣魚(yú)，那么就一定要浪費(fèi)當(dāng)前的 k-t%k 時(shí)間么？

　　假設(shè)你現(xiàn)在已經(jīng)煮了 i 條魚(yú)（包括當(dāng)前煮的這條魚(yú)）；

　　那么，你完全可以在前 i 條魚(yú)中找個(gè) t_j%k（$j \in [1,i]$）大的從而使得浪費(fèi)的 k-t_j%k 時(shí)間盡可能的小；?

　　找 t_j%k 大的就可以使用優(yōu)先級(jí)隊(duì)列了；

　　那么，接下來(lái)就要分析一下優(yōu)先釣?zāi)臈l魚(yú)了；

　　當(dāng)然是優(yōu)先釣煮的時(shí)間較長(zhǎng)的魚(yú)了，因?yàn)樵谥筮@條魚(yú)的時(shí)候，你會(huì)盡可能多的釣上來(lái)其他的魚(yú)，從盡可能多的選擇決策2；

?代碼

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 const int maxn=1e5+50; 5 ll t[maxn]; 6 int n; 7 ll k; 8 9 int main() 10 { 11 ios::sync_with_stdio(0); 12 int T; 13 cin>>T; 14 while(T--) 15 { 16 cin>>n>>k; 17 for(int i=1;i<=n;i++) 18 cin>>t[i]; 19 sort(t+1,t+1+n,greater<int>());///為了保證盡可能多釣魚(yú) 20 ll ans=k;///釣第一條魚(yú)時(shí)間 21 ll cnt=1;///可煮的魚(yú)數(shù) 22 priority_queue<int> pq; 23 for(int i=1;i<=n;i++)///煮魚(yú) 24 { 25 ans+=t[i]; 26 cnt+=t[i]/k;///煮魚(yú)時(shí)所釣的魚(yú) 27 28 ///已經(jīng)沒(méi)有可煮的魚(yú)，需要釣魚(yú) 29 ///由于t是從大到小排序， 30 ///當(dāng)前煮魚(yú)時(shí)已釣不到魚(yú)，那以后也釣不到 31 ///需要額外長(zhǎng)時(shí)間煮魚(yú)以去釣魚(yú) 32 if(cnt<i) 33 { 34 ans+=k-pq.top(); 35 pq.pop(); 36 } 37 pq.push(t[i]%k);///k-t[i]%k小 額外功少 38 } 39 cout<<ans<<"\n"; 40 } 41 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/MMMinoz/p/11431748.html

總結(jié)

以上是生活随笔為你收集整理的HDU 6709“Fishing Master”（贪心+优先级队列）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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