反悔貪心

Work Scheduling G

什么是返回貪心呢，就是先選擇，遇到更好的之后在反悔選擇更好的，這是符合貪心的邏輯的。

#include <bits/stdc++.h>
// https://www.luogu.com.cn/problem/P2949
using namespace std;
struct node
{int d, p;bool operator<(node &b){return d < b.d;}
} w[100005];
long long ans;
priority_queue<int, vector<int>, greater<int>> q;
int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> w[i].d >> w[i].p;}sort(w + 1, w + n + 1); // 按照時間進行排序for (int i = 1; i <= n; i++){// 隊列里面有幾個q.size（） 就是最長的時間了//  如果和時間相等的話,把隊列最前面的取出來進行比較if (w[i].d == q.size()) // 這個如何理解呢？如果w的d就是時間等于q的size（）{if (w[i].p > q.top()){ans -= q.top();q.pop();q.push(w[i].p);ans += w[i].p;}}else{q.push(w[i].p);ans += w[i].p;}}cout << ans;
}

代碼的分析
首先分析題目，在截止時間之前需要完成，我們可以用struct結構體來存儲對應的截止時間和價值，根據截止時間進行排序。for循環遍歷，添加到隊列中去，如果要添加的截止時間等于優先隊列的長度，表示在這個時間內也可以做這件事情，就需要判斷即將添加進來的這件事情的價值和優先隊列中的最小價值比較，如果隊列里面的最小價值小，那么就將其出隊，再把新的添加進去。