#include <stdio.h> #include <stdlib.h> #define MAX_JOBS 1000 struct job { int deadline; int profit; }; struct set { int parent; int size; }; int find(struct set *sets, int i) { if (sets[i].parent != i) { sets[i].parent = find(sets, sets[i].parent); } return sets[i].parent;} void union_sets(struct set *sets, int x, int y) { int root_x = find(sets, x); int root_y = find(sets, y); if (root_x == root_y) { return; } if (sets[root_x].size < sets[root_y].size) { sets[root_x].parent = root_y; sets[root_y].size += sets[root_x].size; } else { sets[root_y].parent = root_x; sets[root_x].size += sets[root_y].size; } } int cmp_jobs(const void *a, const void *b) { struct job *job_a = (struct job *) a; struct job *job_b = (struct job *) b; return job_b->profit - job_a->profit;} int schedule_jobs(struct job *jobs, int n) { struct set sets[MAX_JOBS+1]; int i, j, max_profit = 0; for (i = 1; i <= n; i++) { sets[i].parent = i; sets[i].size = 1; } qsort(jobs, n, sizeof(struct job), cmp_jobs); for (i = 0; i < n; i++) { int slot = find(sets, jobs[i].deadline); if (slot > 0) { union_sets(sets, slot, slot-1); max_profit += jobs[i].profit; } } return max_profit; } int main() { struct job jobs[] = {{4, 70}, {1, 80}, {1, 30}, {1, 100}}; int n = sizeof(jobs) / sizeof(jobs[0]); int max_profit = schedule_jobs(jobs, n); printf("Max profit: %d\n", max_profit); return 0; }逐句解释这一段代码

这段代码是一个在时间约束下进行任务调度的程序。下面逐句解释：

#include <stdio.h> 
#include <stdlib.h> 
#define MAX_JOBS 1000

这是标准头文件和定义一个宏常量。

struct job {
    int deadline;
    int profit;
};

定义了一个结构体，用于存储任务的截止时间和利润。

struct set {
    int parent;
    int size;
};

定义了一个结构体，用于存储并查集的节点信息。

int find(struct set *sets, int i) {
    if (sets[i].parent != i) {
        sets[i].parent = find(sets, sets[i].parent);
    }
    return sets[i].parent;
}

定义了一个函数，用于查找并查集中某个节点的根节点。

void union_sets(struct set *sets, int x, int y) {
    int root_x = find(sets, x);
    int root_y = find(sets, y);
    if (root_x == root_y) {
        return;
    }
    if (sets[root_x].size < sets[root_y].size) {
        sets[root_x].parent = root_y;
        sets[root_y].size += sets[root_x].size;
    } else {
        sets[root_y].parent = root_x;
        sets[root_x].size += sets[root_y].size;
    }
}

定义了一个函数，用于合并并查集中两个集合。

int cmp_jobs(const void *a, const void *b) {
    struct job *job_a = (struct job *) a;
    struct job *job_b = (struct job *) b;
    return job_b->profit - job_a->profit;
}

定义了一个函数，用于比较任务的利润大小。

int schedule_jobs(struct job *jobs, int n) {
    struct set sets[MAX_JOBS+1];
    int i, j, max_profit = 0;
    for (i = 1; i <= n; i++) {
        sets[i].parent = i;
        sets[i].size = 1;
    }
    qsort(jobs, n, sizeof(struct job), cmp_jobs);
    for (i = 0; i < n; i++) {
        int slot = find(sets, jobs[i].deadline);
        if (slot > 0) {
            union_sets(sets, slot, slot-1);
            max_profit += jobs[i].profit;
        }
    }
    return max_profit;
}

定义了一个函数，用于进行任务调度，返回最大利润。

int main() {
    struct job jobs[] = {{4, 70}, {1, 80}, {1, 30}, {1, 100}};
    int n = sizeof(jobs) / sizeof(jobs[0]);
    int max_profit = schedule_jobs(jobs, n);
    printf("Max profit: %d\n", max_profit);
    return 0;
}

主函数，定义了一个任务数组，调用任务调度函数，输出最大利润。