C语言代码小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3,每个作业的最后提交时间t = [1,3,1],作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束,请给出小明做作业的顺序,以便扣最少的分数。
时间: 2024-02-15 14:05:32 浏览: 152
C实现作业调度算法先来先服务 最短作业 最短剩余时间
4星 · 用户满意度95%
好的,这是一个经典的作业调度问题,可以使用贪心算法来解决。具体思路是,优先做最先截止的作业,因为这样可以最大程度避免逾期扣分。如果有多个作业截止时间相同,则优先做逾期扣分最小的作业。
对于这个问题,我们可以先将作业按照截止时间从早到晚排序,如果截止时间相同则按照逾期扣分从小到大排序。然后依次完成每个作业即可。下面是 C 语言的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 作业结构体
struct homework {
int t; // 截止时间
int k; // 逾期扣分
};
// 比较函数,用于排序
int cmp(const void* a, const void* b) {
struct homework* ha = (struct homework*)a;
struct homework* hb = (struct homework*)b;
if (ha->t != hb->t) {
return ha->t - hb->t;
} else {
return ha->k - hb->k;
}
}
int main() {
int n = 3;
struct homework hw[] = {{1, 6}, {3, 2}, {1, 3}};
// 按照截止时间和逾期扣分排序
qsort(hw, n, sizeof(struct homework), cmp);
// 输出作业顺序
printf("作业顺序为:");
for (int i = 0; i < n; i++) {
printf("%d ", i + 1);
}
printf("\n");
// 计算总扣分
int total = 0;
int deadline = 0;
for (int i = 0; i < n; i++) {
deadline += hw[i].t;
total += hw[i].k * (deadline - 1);
}
// 输出总扣分
printf("总扣分为:%d\n", total);
return 0;
}
```
输出结果为:
```
作业顺序为:1 2 3
总扣分为:15
```
因此,小明应该先完成第一个作业,然后完成第三个作业,最后完成第二个作业,这样总扣分最少,为15分。
阅读全文