反悔贪心

· · 个人记录

P2949 [USACO09OPEN] Work Scheduling G

贪心策略：优先完成截止时间小的任务，保证总利润最大化。

维护一个小根堆 q 存储任务完成后可得的利润，则 q 的大小就是当前的时间。当 q 的大小超过当前的截止时间时，弹出队列中最劣的利润。

#include <bits/stdc++.h>
#define int long long

using namespace std;

int n;

struct Node {
    int a, b;
} a[100005];

priority_queue<int, vector<int>, greater<int> > q;

bool cmp(Node a, Node b) {
    return a.a < b.a;
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].a >> a[i].b; 
    }
    sort (a + 1, a + 1 + n, cmp);
    for (int i = 1; i <= n; i++) {
        q.push(a[i].b);
        if (q.size() > a[i].a) {
            q.pop();
        }
    } 
    int sum = 0;
    while (q.size()) {
        sum += q.top();
        q.pop();
    }
    cout << sum;
    return 0;
}

P4053 [JSOI2007] 建筑抢修

贪心策略：优先完成截止时间小的任务，且保证总抢救建筑的时间最小化。

维护一个大根堆 q 存储抢救建筑的时间，t 表示当前的时间，若此时 T_2 \geq t + T_1，则抢救此建筑。否则，判断堆顶建筑使用时间是否大于此时的 T_1。若大于，则证明此时的答案不优，选择反悔不维修堆顶的建筑，改为维修当前建筑。否则不变。

#include <bits/stdc++.h>
#define int long long

using namespace std;

int n;

struct Node {
    int a, b;
} a[150005];

bool cmp(Node a, Node b) {
    return a.b < b.b;
}

priority_queue<int> q;

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].a >> a[i].b;
    }
    sort (a + 1, a + 1 + n, cmp);
    int t = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i].b >= t + a[i].a) {
            t += a[i].a;
            q.push(a[i].a);
        } else {
            if (q.top() > a[i].a) {
                t -= q.top();
                q.pop();
                q.push(a[i].a);
                t += a[i].a;
            }
        }
    }
    cout << q.size();
    return 0;
}

P11328 [NOISG 2022 Finals] Gym Badges

与上一题基本一致。只需要注意当前这一关键词即可。

#include <bits/stdc++.h>
#define int long long

using namespace std;

int n;

struct Node {
    int a, b;
} a[550005];

bool cmp(Node a, Node b) {
    return b.a + b.b > a.a + a.b;
}

priority_queue<int> q;

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].a;
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i].b;
    }
    sort (a + 1, a + 1 + n, cmp);
    int t = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i].b >= t) {
            t += a[i].a;
            q.push(a[i].a);
        } else {
            if (q.top() > a[i].a) {
                t -= q.top();
                q.pop();
                q.push(a[i].a);
                t += a[i].a;
            }
        }
    }
    cout << q.size();
    return 0;
}

P3545 [POI 2012] HUR-Warehouse Store

贪心策略：优先完成数量小的顾客的要求。

维护大根堆 q 存储顾客的数量要求。当当前数量储存不够时，拿出堆顶的需求交换即可。

#include <bits/stdc++.h>
#define int long long

using namespace std;

int n;

struct Node {
    int a, b;
    bool operator < (const Node &nxt) const {
        return b < nxt.b;
    }
} a[550005];

priority_queue<Node> q;
set<int> s;

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].a;
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i].b;
    }
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += a[i].a;
        if (sum >= a[i].b) {
            sum -= a[i].b;
            q.push({i, a[i].b});
        } else if (!q.empty() && sum < a[i].b && q.top().b > a[i].b) {
            sum += (q.top().b - a[i].b);
            q.pop();
            q.push({i, a[i].b});
        }
    }
    cout << q.size() << '\n';
    while (!q.empty()) {
        cout << q.top().a << ' ';
        q.pop();
    }
    return 0;
}

U546879 股票交易 及 CF865D Buy Low Sell High

贪心策略：Buy Low Sell High

维护小根堆 q 存储价钱方便后面反悔。

首先每天要花 a_i 的钱数买下一股。

接着，因为需要遵循 Buy Low Sell High 的原则，所以应该是之前买入最便宜的要最大利益化卖出。所以，若当前的价钱比之前的价钱还要高，就将两者交换，并且再压入队列。因为此时是代表之前的价钱的一股股票。

#include <bits/stdc++.h>
#define int long long

using namespace std;

int n, sum;
priority_queue<int, vector<int>, greater<int> > q;

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        q.push(x);
        if (q.top() < x) {
            sum = sum - q.top() + x;
            q.pop();
            q.push(x);
        }
    }
    cout << sum;
    return 0;
}