贪心算法实现最佳任务调度实验_任务调度问题一个单位时间任务是恰好需要一个单位时间完成的任务。给定一个单位时

题目描述

  一个单位时间任务是恰好需要一个单位时间完成的任务。给定一个单位时间任务的有限集S。关于S 的一个时间表用于描述S 中单位时间任务的执行次序。时间表中第1 个任务从时间0 开始执行直至时间1 结束，第2 个任务从时间1 开始执行至时间2 结束，…，第n个任务从时间n-1 开始执行直至时间n结束。具有截止时间和误时惩罚的单位时间任务时间表问题可描述如下：
     (1) n 个单位时间任务的集合S={1,2,…,n}（n≤500）；
     (2) 任务 i 的截止时间d[i],1≤ i ≤n，1 ≤ d[i] ≤ n，即要求任务i在时间d[i]之前结束；
     (3) 任务 i 的误时惩罚1≤ w[i] < 1000，1 ≤ i ≤ n,即任务 i 未在时间d[i]之前结束将招致w[i]的惩罚；若按时完成则无惩罚。
  任务时间表问题要求确定S 的一个时间表（最优时间表）使得总误时惩罚达到最小。

输入数据

  第一行是正整数 n ，表示任务数。接下来的 2 行中，每行有 n 个正整数，分别表示各任务的截止时间和误时惩罚。

输出数据

        将计算出的最小总误时惩罚输出

样例输入

7
4 2 4 3 1 4 6
70 60 50 40 30 20 10

样例输出

50

解题思路

        为了达到最小的误时惩罚，按照贪心策略，要先去按时完成或提前完成惩罚较大的任务。若一个时间片上已经安排了按时完成的或者有着较大罚时的任务，那么，较小惩罚的任务则需要提前完成（该任务应放在紧邻的上一个时间片完成，若这个时间片也有任务，继续往前移，直到有空闲的时间片可以执行这个任务，否则，这个任务会带来罚时，就在返回的总罚时上加上这个罚时）。

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
 
const int N = 1e5 + 10;
 
int n;
bool visited[N];
 
struct Task
{
    int d;
    int w;
} task[N];
 
bool cmp(Task &t1, Task &t2)
{
    return t1.w > t2.w;
}
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> task[i].d;
    for (int i = 0; i < n; ++i) cin >> task[i].w;
 
    sort(task, task + n, cmp);
 
    int result = 0;
    for (int i = 0; i < n; ++i)
    {
        bool mark = false;
        for (int j = task[i].d; j > 0; --j)
        {
            if (!visited[j - 1])
            {
                visited[j - 1] = true;
                mark = true;
                break;
            }
        }
        if (!mark) result += task[i].w;
    }
 
    cout << result << endl;
    return 0;
}
 
/*
输入：
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
输出：
50
*/

ps：实验指导书上还有第二小问：将每个 Wi 替换为 max{W1,W2……Wn}-Wi 运行算法、比较并分析结果。（此处就是把w[i]修改一下即可，代码实现如下）

#include <iostream>
#include <algorithm>
using namespace std;
 
const int N = 1e5 + 10;
 
int n;
bool visited[N];
 
struct Task
{
    int d;
    int w;
} task[N];
 
bool cmp(Task &t1, Task &t2)
{
    return t1.w > t2.w;
}
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> task[i].d;
 
    int max_w = 0;
    for (int i = 0; i < n; ++i) 
    {
        cin >> task[i].w;
        max_w = max(max_w, task[i].w);
    }
 
    for (int i = 0; i < n; ++ i) task[i].w = max_w - task[i].w;
 
    sort(task, task + n, cmp);
 
    int result = 0;
    for (int i = 0; i < n; ++i)
    {
        bool mark = false;
        for (int j = task[i].d; j > 0; --j)
        {
            if (!visited[j - 1])
            {
                visited[j - 1] = true;
                mark = true;
                break;
            }
        }
        if (!mark) result += task[i].w;
    }
 
    cout << result << endl;
    return 0;
}
 
/*
输入：
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
输出：
10
*/