用c语言和算法知识解决以下问题:小明上学,老师布置了*n.个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n.=.3,每个作业的最后提交时间t=.[1,3.1],作业逾期扣分k*=.[6,2,3]。以输入n*=.0时作为结束,请给出小明做作业的顺序,以便扣最少的分数。
时间: 2024-02-19 16:58:14 浏览: 23
这是一个经典的贪心算法问题,可以使用以下思路解决:
1. 将每个作业按照最后提交时间从早到晚排序。
2. 依次考虑每个作业,如果当前时间可以完成该作业,则直接完成;否则放弃该作业,考虑下一个作业。
3. 如果所有作业都无法完成,则返回扣分最少的作业。
具体实现可以使用结构体来表示每个作业,包括最后提交时间和逾期扣分。然后按照最后提交时间排序,依次遍历每个作业,判断是否可以完成,如果可以则完成,否则继续考虑下一个作业。如果所有作业都无法完成,则返回扣分最少的作业。
以下是一份C语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义作业结构体
typedef struct {
int t; // 最后提交时间
int k; // 逾期扣分
} Job;
// 按照最后提交时间从早到晚排序
int cmp(const void *a, const void *b) {
return ((Job *)a)->t - ((Job *)b)->t;
}
int main() {
int n = 0;
Job jobs[100];
int i, j;
// 读入作业信息
while (1) {
printf("请输入作业最后提交时间和逾期扣分,以空格分隔(输入0结束):");
scanf("%d", &jobs[n].t);
if (jobs[n].t == 0) {
break;
}
scanf("%d", &jobs[n].k);
n++;
}
// 按照最后提交时间排序
qsort(jobs, n, sizeof(Job), cmp);
// 计算最少扣分
int time = 1; // 当前时间
int min_k = 1e9; // 最少扣分
int min_j = -1; // 最少扣分的作业
for (i = 0; i < n; i++) {
if (time <= jobs[i].t) {
// 当前时间可以完成该作业
time++;
} else {
// 当前时间无法完成该作业
if (jobs[i].k < min_k) {
// 更新最少扣分
min_k = jobs[i].k;
min_j = i;
}
}
}
if (min_j == -1) {
// 所有作业都可以按时完成
printf("小明可以按时完成所有作业!\n");
} else {
// 返回扣分最少的作业
printf("小明应该先完成最后提交时间为%d的作业,扣分为%d。\n", jobs[min_j].t, jobs[min_j].k);
}
return 0;
}
```
输入样例:
```
请输入作业最后提交时间和逾期扣分,以空格分隔(输入0结束):1 6
请输入作业最后提交时间和逾期扣分,以空格分隔(输入0结束):3 3
请输入作业最后提交时间和逾期扣分,以空格分隔(输入0结束):1 2
请输入作业最后提交时间和逾期扣分,以空格分隔(输入0结束):0
```
输出样例:
```
小明应该先完成最后提交时间为3的作业,扣分为3。
```