用c语言和算法知识解决以下问题:小明上学,老师布置了n.个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n.=.3,每个作业的最后提交时间t=.[1,3.1],作业逾期扣分k=.[6,2,3]。以输入n*=.0时作为结束,请给出小明做作业的顺序,以便扣最少的分数,并输出作业顺序
时间: 2024-02-19 21:58:19 浏览: 84
这个问题可以使用贪心算法来解决。具体步骤如下:
1. 将所有作业按照最后提交时间从小到大排序。
2. 依次遍历每个作业,如果当前时间小于等于最后提交时间,就直接做这个作业,否则就不做这个作业。
3. 如果不能做当前作业,就将当前作业放到一个待处理列表中。
4. 当所有作业都遍历完之后,对待处理列表按照逾期扣分从大到小排序。
5. 依次遍历待处理列表,选择逾期扣分最大的作业进行做。
以下是 C 语言的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int t; // 最后提交时间
int k; // 逾期扣分
} Job;
int cmp(const void* a, const void* b) {
Job* p1 = (Job*)a;
Job* p2 = (Job*)b;
return p1->t - p2->t;
}
int main() {
int n = 0;
Job jobs[100];
while (1) {
printf("请输入第 %d 个作业的最后提交时间和逾期扣分,以空格分隔(例如:3 2):", n + 1);
int t, k;
scanf("%d %d", &t, &k);
if (t == 0 || k == 0) {
break;
}
jobs[n].t = t;
jobs[n].k = k;
n++;
}
qsort(jobs, n, sizeof(Job), cmp);
int score = 0;
for (int i = 0; i < n; i++) {
if (i + 1 <= jobs[i].t) {
score += jobs[i].k * (jobs[i].t - i - 1);
} else {
jobs[n++] = jobs[i];
}
}
qsort(jobs + n - (n - score), n - score, sizeof(Job), cmp);
printf("作业顺序为:");
for (int i = 0; i < n; i++) {
if (i < score) {
printf("%d ", i + 1);
} else {
printf("%d ", n - (i - score));
}
}
printf("\n");
return 0;
}
```
输入样例:
```
请输入第 1 个作业的最后提交时间和逾期扣分,以空格分隔(例如:3 2):2 6
请输入第 2 个作业的最后提交时间和逾期扣分,以空格分隔(例如:3 2):3 2
请输入第 3 个作业的最后提交时间和逾期扣分,以空格分隔(例如:3 2):1 3
请输入第 4 个作业的最后提交时间和逾期扣分,以空格分隔(例如:3 2):0 0
```
输出样例:
```
作业顺序为:2 3 1
```
阅读全文