带有期限的作业排序要解决的是操作系统中单机、无资源约束且每个作业可在等量时间内完成的作业调度问题，形式化描述为： ①只能在一台机器上处理n个作业，每个作业i=1,...,n均可在单位时间内完成； ②每个作业i都有一个期限值d i ​ >0，（d i ​ 是整数）； ③当且仅当作业i在它的截止期限前被完成时获得p i ​ >0的效益； 问题的可行解是这n个作业的一个子集合J。J中的每个作业都能在各自的截止期限之前完成，产生一个作业效益之和∑p i ​ 。具有最大效益值的可行解就是最优解。 要求用更快的作业排序算法（利用集合树方法）实现。 输入格式: 第一行为一个不超过200的正整数n，表示作业的个数； 接下来的n行，每行两个正整数（中间用空格隔开），表示每个作业i的截止期限d i ​ 和按期完成产生的效益p i ​ 。输入样例1: 4 1 20 2 15 2 100 1 10 输出样例1: 120 1 3

这道题可以用集合树法来解决。集合树是一种特殊的线段树，每个节点表示一个区间，并维护该区间内的元素集合。具体来说，对于一个区间 [l, r]，设其对应的节点为 node，那么 node 中存储的就是所有在区间 [l, r] 中出现过的元素。

在本题中，我们可以将每个作业看成一个元素，将作业的截止期限作为元素的权值，并将所有作业按照截止期限从大到小排序。然后依次将每个作业插入集合树中，如果插入后集合树中的元素个数大于作业的截止期限，则说明该作业不能完成，跳过该作业，否则将该作业纳入最优解中。

具体的实现过程如下：

1. 读入作业的数量n以及每个作业的截止期限di和效益pi。

2. 将所有作业按照截止期限从大到小排序。

3. 初始化集合树，节点数为n*2-1，每个节点表示一个区间。

4. 依次遍历每个作业i，将其插入集合树中，然后检查集合树中元素的个数是否大于作业i的截止期限。如果元素个数大于截止期限，则将该作业从集合树中删除，否则将该作业的效益加入最优解中。

5. 输出最优解的效益之和以及选择的作业编号。

下面是 C++ 的代码实现：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 205;

struct Job {
    int d, p, id;
    bool operator < (const Job &t) const {
        return d > t.d;
    }
} jobs[MAXN];

struct SegmentTree {
    int l, r, cnt;
    SegmentTree *ls, *rs;
    SegmentTree(int l, int r) : l(l), r(r), cnt(0), ls(nullptr), rs(nullptr) {}
    ~SegmentTree() {
        delete ls, delete rs;
    }
    void update(int x) {
        cnt += x;
        if (l < r) {
            int mid = (l + r) >> 1;
            if (x <= mid - l) {
                if (!ls) ls = new SegmentTree(l, mid);
                ls->update(x);
            } else {
                if (!rs) rs = new SegmentTree(mid + 1, r);
                rs->update(x - (mid - l + 1));
            }
        }
    }
    int query(int x) {
        if (l == r) return l;
        int mid = (l + r) >> 1;
        if (x <= ls->cnt) return ls->query(x);
        return rs->query(x - ls->cnt);
    }
};

int main() {
    int n, i, sum = 0;
    SegmentTree *root;

    cin >> n;

    for (i = 0; i < n; i++) {
        cin >> jobs[i].d >> jobs[i].p;
        jobs[i].id = i + 1;
    }

    sort(jobs, jobs + n);

    root = new SegmentTree(1, n);

    for (i = 0; i < n; i++) {
        int pos = root->query(1);
        if (pos <= jobs[i].d) {
            root->update(1);
            sum += jobs[i].p;
        }
    }

    cout << sum << endl;

    for (i = 0; i < n; i++)
        if (root->query(i + 1) <= jobs[i].d)
            cout << jobs[i].id << ' ';
    cout << endl;

    delete root;

    return 0;
}