带有期限的作业排序要解决的是操作系统中单机、无资源约束且每个作业可在等量时间内完成的作业调度问题，形式化描述为： ①只能在一台机器上处理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 ​ 。 输出格式: 第一行给出最优解的效益值。 第二行按照时间片分配顺序输出最优解J中的作业，中间用空格隔开，最后一个作业后面不要加空格。用C语言实现

这是一个经典的贪心算法问题，可以使用集合树（Disjoint Set Union）方法实现。具体思路是：

1. 按照截止期限从小到大排序。

2. 对于每个作业，将其加入到当前能完成的最晚的位置。如果该位置已经被占用，则往前找能够完成的位置。如果没有可用位置，则该作业不能完成。

3. 最后统计完成的作业的效益之和即为最优解的效益值。

以下是具体的C语言实现代码：

#include <stdio.h>
#include <stdlib.h>

#define MAXN 200

struct Job {
    int d; // 截止期限
    int p; // 效益
    int id; // 作业编号
};

int n; // 作业个数
struct Job job[MAXN]; // 作业数组

int parent[MAXN+1]; // 集合树的父节点
int maxd; // 最晚完成时间

// 集合树的初始化
void init() {
    for (int i = 0; i <= n; ++i) {
        parent[i] = i;
    }
    maxd = 0;
}

// 集合树的查找
int find(int x) {
    if (parent[x] == x) {
        return x;
    }
    return parent[x] = find(parent[x]);
}

// 集合树的合并
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        parent[x] = y;
    }
}

// 按照截止期限从小到大排序
int cmp(const void *a, const void *b) {
    struct Job *j1 = (struct Job *)a;
    struct Job *j2 = (struct Job *)b;
    return j1->d - j2->d;
}

int main() {
    // 读入作业
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &job[i].d, &job[i].p);
        job[i].id = i + 1;
    }

    // 排序
    qsort(job, n, sizeof(struct Job), cmp);

    // 集合树的初始化
    init();

    // 逐个处理每个作业
    int sum = 0; // 最优解的效益值
    int cnt = 0; // 已完成的作业个数
    int ans[MAXN]; // 最优解的作业编号
    for (int i = 0; i < n; ++i) {
        int t = find(job[i].d); // 能够完成作业的最晚时间
        if (t > 0) {
            sum += job[i].p;
            ++cnt;
            ans[cnt-1] = job[i].id;
            merge(t, t-1); // 将能够完成作业的时间段合并
            if (t > maxd) {
                maxd = t;
            }
        }
    }

    // 输出结果
    printf("%d\n", sum);
    for (int i = 0; i < cnt; ++i) {
        printf("%d", ans[i]);
        if (i == cnt-1) {
            printf("\n");
        } else {
            printf(" ");
        }
    }

    return 0;
}