「一本通 1.1 练习 4」家庭作业 题解

题目概述

LOJ #10008. 「一本通 1.1 练习 4」家庭作业

老师在开学第一天就把所有作业都布置了，每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为 $10$，要求在 $6$ 天内交，那么要想拿到这 $10$ 学分，就必须在第 $6$ 天结束前交。

每个作业的完成时间都是只有一天。例如，假设有 7 次作业的学分和完成时间如下：

作业号	期限	学分
$1$	$1$	$6$
$2$	$1$	$7$
$3$	$3$	$2$
$4$	$3$	$1$
$5$	$2$	$4$
$6$	$2$	$5$
$7$	$6$	$1$

最多可以获得 $15$ 学分，其中一个完成作业的次序为 $2,6,3,1,7,5,4$，注意可能还有其他方法。

你的任务就是找到一个完成作业的顺序获得最大学分。

显然的贪心，先按学分 $s$ 从大到小，再按期限 $d$ 从后到前

考虑要安排一个作业，显然是越晚越好，故用一个二分区间，用一个数据结构查询、修改

这里选择二分套树状数组

int l = 1, r = a[i].d;
// st 为树状数组
if (st.sum(r) == 0) // 无法插入
    continue;
else {
    ans += a[i].s;
    while (l <= r) {
        if (l == r) {
            st.add(l, -1);
            break;
        }
        int mid = (l + r) / 2;
        if (st.query(mid + 1, r) > 0)
            l = mid + 1;
        else
            r = mid;
    }
}

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::make_pair;
using std::pair;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned int ui;

const int T = 7.5 * 1e5;

struct BIT {
    ui c[T], n = 7 * 1e5;
    int lowbit(int x) { return x & -x; }
    void add(int pos, ui x) {
        for (int i = pos; i <= n; i += lowbit(i)) c[i] += x;
    }
    ui sum(int n) {
        ui ret = 0;
        for (int i = n; i > 0; i -= lowbit(i)) ret += c[i];
        return ret;
    }
    ui query(int l, int r) { return sum(r) - sum(l - 1); }
} st;

struct Node {
    int s, d;
    bool operator<(const Node& b) const {
        return (s == b.s ? d > b.d : s > b.s);
    }
} a[1000010];

int main() {
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    int n, ans = 0;
    cin >> n;
    rep(i, 1, n) cin >> a[i].d >> a[i].s, st.add(i, 1);
    std::sort(a + 1, a + 1 + n);
    rep(i, 1, n) {
        int l = 1, r = a[i].d;
        if (st.sum(r) == 0)
            continue;
        else {
            ans += a[i].s;
            while (l <= r) {
                if (l == r) {
                    st.add(l, -1);
                    // cerr << l << endl;
                    break;
                }
                int mid = (l + r) / 2;
                if (st.query(mid + 1, r) > 0)
                    l = mid + 1;
                else
                    r = mid;
            }
        }
    }
    cout << ans << endl;
    return 0;
}