LOJ 10008

LOJ #10008. 「一本通 1.1 练习 4」家庭作业
传送门：LOJ 10008 | SSOIER 1430

题目大意

已知：有 \(n\) 项作业，每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为 \(10\)，要求在 \(6\) 天内交，那么要想拿到这 \(10\) 学分，就必须在第 \(6\) 天结束前交。
求解：找到一个完成作业的顺序获得最大学分。

解法

本题是贪心算法的典型例题，在此介绍 \(3\) 种方法解决此类问题。

法1：反悔贪心

100 AC 提交记录 | 按照截止时间从小到大排序，如果放不下尝试替换放好的元素中奖励最小的

#include <bits/stdc++.h>
#define lli long long int
using namespace std;
typedef pair<int, int> pii;
const int MAXn = 1e6 + 9;
const int MAXdl = 7e5 + 9;
priority_queue<pii, vector<pii>, greater<pii> > pq;    // first: v; second: time
vector<pii> d;    // first: deadline; second: v

bool cmp(const pii & x, const pii & y) {
    if(x.first == y.first) return x.second > y.second;
    return x.first < y.first;
}

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1, ia, ib; i <= n; i ++) {
        scanf("%d%d", &ia, &ib);
        d.push_back({ia, ib});
    }
    sort(d.begin(), d.end(), cmp);
    lli ans = 0;
    int t = 1;
    for(pii x : d) {
        if(x.first < t) {
            if(!pq.empty() && pq.top().first < x.second) {
                int tt = pq.top().second;
                ans -= pq.top().first;
                pq.pop();
                pq.push({x.second, tt});
                ans += x.second;
            }
            else continue;
        }
        else {
            pq.push({x.second, t});
            ans += x.second;
            t ++;
        }
    }
    printf("%lld", ans);
    return 0;
}

法2：枚举每个元素

80 TLE 提交记录 | 按照奖励大小排序，优先安排奖励数最大的，且尽量靠后地安排

#include <bits/stdc++.h>
#define lli long long int
using namespace std;
typedef pair<int, int> pii;
const int MAXn = 1e6 + 9;
bool ved[MAXn];
vector<pii> d;    // first: deadline; second: v

bool cmp(const pii & x, const pii & y) {
    if(x.second == y.second) return x.first > y.first;
    return x.second > y.second;
}

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1, ia, ib; i <= n; i ++) {
        scanf("%d%d", &ia, &ib);
        d.push_back({ia, ib});
    }
    sort(d.begin(), d.end(), cmp);
    lli ans = 0;
    for(pii x : d) {
        for(int i = x.first; i >= 1; i --)
            if(!ved[i]) {
                ved[i] = true;
                ans += x.second;
                break;
            }
    }
    printf("%lld", ans);
    return 0;
}

使用枚举每个元素的方法并不能通过此题，但对于此类贪心问题是一个可以考虑的选择，如 LOJ 10004. 「一本通 1.1 例 5」智力大冲浪 可以 AC。

LOJ 10004. 「一本通 1.1 例 5」智力大冲浪

传送门：LOJ 10004 | 洛谷 P1230

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXn = 500 + 9;
bool ved[MAXn];
vector<pii> d;    // first: deadline; second: v

bool cmp(const pii & x, const pii & y) {
    if(x.second == y.second) return x.first > y.first;
    return x.second > y.second;
}

int main() {
    int m, n;
    scanf("%d%d", &m, &n);
    for(int i = 0, ia; i < n; i ++) {
        scanf("%d", &ia);
        d.push_back({ia, 0});
    }
    for(int i = 0; i < n; i ++) {
        scanf("%d", &d[i].second);
    }
    sort(d.begin(), d.end(), cmp);
    for(int i = 0; i < n; i ++) {
        int dl = d[i].first;
        bool can = false;
        for(int t = dl; t >= 1; t --)
            if(!ved[t]) {
                ved[t] = true;
                can = true;
                break;
            }
        if(!can) {
            m -= d[i].second;
        }
    }
    printf("%d", m);
    return 0;
}

法3：枚举时间

100 AC 提交记录 | 枚举所有时间，并放入能放入的元素中奖励数最大的。

#include <bits/stdc++.h>
#define lli long long int
using namespace std;
const int MAXn = 1e6 + 9;
vector<int> d[MAXn];    // d[x]: 死线为 x 的所有奖励
priority_queue<int> pq;

int main() {
    int n, maxdl = 1;
    scanf("%d", &n);
    for(int i = 1, ia, ib; i <= n; i ++) {
        scanf("%d%d", &ia, &ib);
        d[ia].push_back(ib);
        maxdl = max(maxdl, ia);
    }
    lli ans = 0;
    for(int i = maxdl; i >= 1; i --) {
        for(int v : d[i]) pq.push(v);
        if(!pq.empty()) ans += pq.top(), pq.pop();
    }
    printf("%lld", ans);
    return 0;
}

考虑到本题截止时间的数据范围为 \(1\le t \le 1 \times 10^5\)，使用上述代码不会出现 MLE 的情况。如果数据范围较大，可以使用离散化算法，将截止时间数组离散化为一个更小的范围，就可以存放到容器中了。

类似的题目 P2949 [USACO09OPEN] Work Scheduling G 使用离散化算法后 92 MLE 代码：

#include <bits/stdc++.h>
#define lli long long int
using namespace std;
const int MAXn = 1e5 + 9;
vector<int> dl, v, lsh;
vector<int> d[MAXn];
priority_queue<int> pq;
map<int, int> sl, ls;

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1, ia, ib; i <= n; i ++)
        scanf("%d%d", &ia, &ib),
        dl.push_back(ia),
        v.push_back(ib);
    lsh.assign(dl.begin(), dl.end());
    sort(lsh.begin(), lsh.end());
    int mxdl = lsh.back();
    auto it = unique(lsh.begin(), lsh.end());
    for(int i = 0; i < n; i ++)
        ls[dl[i]] = distance(lsh.begin(), lower_bound(lsh.begin(), it, dl[i])) + 1;
    for(int i = 0; i < n; i ++)
        d[ls[dl[i]]].push_back(v[i]);
    lli ans = 0;
    for(int i = mxdl; i >= 1; i --) {
        if(ls[i]) for(int v : d[ls[i]]) pq.push(v);
        if(!pq.empty()) ans += pq.top(), pq.pop();
    }
    printf("%lld", ans);
    return 0;
}

该题可使用反悔贪心通过

100 AC 提交记录

#include <bits/stdc++.h>
#define lli long long int
using namespace std;
typedef pair<int, int> pii;
priority_queue<pii, vector<pii>, greater<pii> > pque;    // first: value; second: position
vector<pii> d;    // first: endtime; second: value

bool cmpd(const pii & x, const pii & y) {
    if(x.first == y.first) return x.second > y.second;
    return x.first < y.first;
}

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1, ia, ib; i <= n; i ++) {
        scanf("%d%d", &ia, &ib);
        d.push_back({ia, ib});
    }
    sort(d.begin(), d.end(), cmpd);
    lli ans = 0;
    int p = 1;
    for(pii x : d) {
        if(x.first < p) {
            if(!pque.empty() && x.second > pque.top().first) {
                int pp = pque.top().second;
                ans -= pque.top().first;
                pque.pop();
                pque.push({x.second, pp});
                ans += x.second;
            }
            else continue;
        }
        else {
            pque.push({x.second, p});
            ans += x.second;
            p ++;
        }
    }
    printf("%lld", ans);
    return 0;
}