題干：

鏈接：https://ac.nowcoder.com/acm/contest/369/B
來源：牛客網
?

小A手頭有 n 份任務，他可以以任意順序完成這些任務，只有完成當前的任務后，他才能做下一個任務

第 i 個任務需要花費??xixi?的時間，同時完成第 i 個任務的時間不能晚于?yiyi ，時間掌控者向小A提出了一個條件：如果完成第 i 個任務的時間本應是 t ，但小A支付 m 個金幣的話，他可以幫助小A在?t?m×zit?m×zi? 時刻完成第 i 個任務，?zizi 是時間參數，會在輸入中給出

小A想按時完成所有任務，請你幫他制定一個花費金幣最少的方案

注意：不能使得某個任務的花費時間小于 0 ,花費的金幣可以不是整數

輸入描述:

第一行一個整數 n ，表示小A的任務數量 接下來n行，每行三個整數，分別表示?zi,xi,yizi,xi,yi

輸出描述:

一行一個實數，表示小A最少需要花費的金幣數，四舍五入保留一位小數

示例1

輸入

復制

5 1 1 2 1 1 3 1 2 4 1 1 4 1 2 5

輸出

復制

2.0

說明

在1時刻完成第一個任務,2時刻完成第二個任務,4時刻完成第三個任務,花費1金幣在4時刻完成第四個任務,花費1金幣在5時刻完成第五個任務

備注:

1≤n≤2×1051≤n≤2×105

1≤xi,zi≤3×1031≤xi,zi≤3×103

1≤yi≤105

解題報告：

貪心。

以完成時間為關鍵字從小到大排序(可以交換兩個完成時間不同的任務來證明這樣的正確性)，按這個順序來做任務，同時維護一個關于 zi?的大根堆，如果規定時間內完不成任務，就從堆里取出 zi 最大的任務來花費金幣，維護每個任務的剩余時間，如果花費金幣后剩余時間不為 0 則重新push入堆

其實是連續兩次貪心的決策：

首先貪心按照y關鍵字排序來確定完成任務的順序。

然后如果有任務已經在當前局面下完成不了了，那也不一定要讓他提前，也可以選擇讓前面已經完成過的任務提前完成。這也就是第二步貪心的決策。這一過程是用優先隊列動態維護的。

注意，雖然這樣看起來好像是同一個任務分開時間完成的(反正代碼看起來應該是這樣的)（因為題目要求一個任務需要連續完成，也就是不能這個任務做一半了去開另一個任務），但是實際上執行的時候是連續完成的，因為這里在優先隊列中作差的不是任務，而是任務提前完成的時間。也就是假設這個任務需要五分鐘完成，我們可以讓他先提前兩分鐘完成，后面下了一個命令，要求他在提前十分鐘完成，但是沒辦法了只能再提前三分鐘了，所以就先能提前多少就提前多少，是在不夠了再去優先隊列中找z第二大的元素去提前完成。

這種操作相當于是用優先隊列推遲了操作，也是提供了反悔的機會，當后面確實需要反悔的時候，可以貪心的選擇一個最優的決策進行反悔。

復雜度 O(nlogn)

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; typedef pair<ll,ll> PLL; struct Node {ll z,x,y;//第 i 個任務需要花費 xi 的時間，同時完成第 i 個任務的時間不能晚于 yi ,zi是時間參數 } node[MAX]; bool cmp(Node a,Node b) {return a.y < b.y; } int main() {int n;cin>>n;for(int i = 1; i<=n; i++) cin>>node[i].z>>node[i].x>>node[i].y;sort(node+1,node+n+1,cmp);double ans = 0;ll cur = 0;priority_queue<PLL> pq;for(int i = 1; i<=n; i++) {pq.push(pm(node[i].z,node[i].x));cur += node[i].x;while(cur > node[i].y) {PLL now = pq.top();pq.pop();ll t = min(now.second,cur - node[i].y);ans += 1.0*t/now.first;cur -= t;now.second -= t;if(now.second) pq.push(now);}}printf("%.1f\n",ans);return 0 ;}

?

總結

以上是生活随笔為你收集整理的【牛客 - 369B】小A与任务（贪心，优先队列）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。