单位时间的调度问题
题目描述：
现有一个机器要处理n项任务，每项任务都可以在一个单位时间内完成。每项任务有截止时间(d1, d2,,…, dn)，和超过截止时间内未完成的惩罚因子(w1, w2,,…, wn)。求所有任务排列中最小的惩罚因子和。例如若有3项任务，其截止时间为(2,2,2)，惩罚因子为(6,7,8)。排列123,132,213,231,312,321的惩罚因子和为分别是8,7,8,6,7,6。可见6是所有任务排列中惩罚因子最小和为6。
输入格式：
共三行，第一行为一个整数n（0<n<=10000），第二行是n个正整数d1, d2,,…, dn（保证在int内），第三行是n个正整数w1, w2,,…, wn（保证在int内）。
输出格式：
一行一个数，即最小惩罚因子和。
本题显然是贪心实现，具体怎么贪心呢！大概的思路就是：优先考虑惩罚更重的任务，在考虑每一个任务的时候安排它在最靠近dll的时间完成。可以证明此题满足贪心选择性质，如此贪心策略也是正确的。
1、数据预处理
首先将任务用一个结构体表示，包含任务的 ddl 和惩罚 weight。然后创建一个任务的 thing[]数组，并且对数组以weight为关键字降序排序。
struct node {
int deadLine; //ddl
int weight; //惩罚
} thing[MAXN];
bool cmp(struct node x, struct node y) {
if (x.weight == y.weight) //当惩罚一样时
return x.deadLine < y.deadLine; //优先ddl在前面的
else
return x.weight > y.weight; //优先惩罚更重的
}
对输入的处理和各种数组的初始化我放到一个 Init() 函数中实现。为了方便安排时间段，定义一个时间槽：用数组 done[]来表示。若 done[]= true，则表示第 i 个单位时间段是空闲的。所以应该初始化 done 全为 true，每次分配一个时间就赋值为 false 以避免冲突。
void Init() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &thing[i].deadLine);
for (int i = 1; i <= n; i++)
scanf("%d", &thing[i].weight);
for(int i = 0;i <= n; i++)
done[i] = true;
}
2、贪心实现
按照我们排序后的顺序（即优先考虑惩罚更重的任务），依次考虑每一个任务，安排它在最靠近 dll 的时间完成。如果找不到，就无法完成。
/* 为任务t寻找合适的时间
* 找不到则返回false */
bool Done(struct node t) {
//找到最接近ddl的空闲时间段
for(int i = t.deadLine; i >= 1; i--)
if(done[i]) {
done[i] = false;
return true;
}
//找不到则返回假
return false;
}
int Calc() {
sort(thing + 1, thing + n + 1, cmp); //对任务以惩罚为关键字排序
int ans= 0;
for(int i = 1; i <= n; i++) {
if(!Done(thing[i])) //对于找不到合适时间的任务
ans += thing[i].weight; //加入惩罚
}
return ans;
}
下面附上完整代码与测试用例：
#include <cstdio>
#include <algorithm>
#define MAXN 10050
using namespace std;
int n;
bool done[MAXN]; //第i个时间段是否有空
struct node {
int deadLine; //ddl
int weight; //惩罚
} thing[MAXN];
bool cmp(struct node x, struct node y) {
if (x.weight == y.weight) //当惩罚一样时
return x.deadLine < y.deadLine; //优先ddl在前面的
else
return x.weight > y.weight; //优先惩罚更重的
}
void Init() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &thing[i].deadLine);
for (int i = 1; i <= n; i++)
scanf("%d", &thing[i].weight);
for(int i = 0;i <= n; i++)
done[i] = true;
}
/* 为任务t寻找合适的时间
* 找不到则返回false */
bool Done(struct node t) {
//找到最接近ddl的空闲时间段
for(int i = t.deadLine; i >= 1; i--)
if(done[i]) {
done[i] = false;
return true;
}
//找不到则返回假
return false;
}
int Calc() {
sort(thing + 1, thing + n + 1, cmp); //对任务以惩罚为关键字排序
int ans= 0;
for(int i = 1; i <= n; i++) {
if(!Done(thing[i])) //对于找不到合适时间的任务
ans += thing[i].weight; //加入惩罚
}
return ans;
}
int main() {
Init();
printf("%d
", Calc());
}
测试用例
4
1 1 3 4
7 8 9 10
输出：7
4
2 2 2 1
16 7 8 2
输出：9
5
5 5 2 2 3
12 3 1 2 9
输出：0
6
3 3 3 4 4 4
7 8 9 12 1 3
输出：4
8
1 1 1 2 2 2 3 3
1 2 3 1 3 3 5 4
输出：10
3
2 2 2
6 7 8
输出：6
4
1 1 2 3
1 2 7 9
输出：1
6
1 3 4 4 6 1
21 2 20 9 25 15
输出：15
6
6 1 4 1 4 3
0 4 5 10 16 23
输出：4
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
输出：50