单位时间的调度问题 | 贪心

朴灿烈づ我的快乐病毒、 2023-02-20 07:36 3阅读 0赞

更新一下今天 “计算理论与算法设计” 期末考试的三道编程题，没有测试用例的题真是太蓝受了。分享一下我考试时的思路，最后也给出了我编写的自测用例。仅供参考，如有错误还请指出~

--------------------

> ## 02 ##
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <td>成绩</td> 
>    <td>15</td> 
>    <td>开启时间</td> 
>    <td>2020年06月24日 星期三 15:10</td> 
>   </tr> 
>   <tr> 
>    <td>折扣</td> 
>    <td>0.8</td> 
>    <td>折扣时间</td> 
>    <td>2020年06月24日 星期三 18:30</td> 
>   </tr> 
>   <tr> 
>    <td>允许迟交</td> 
>    <td>否</td> 
>    <td>关闭时间</td> 
>    <td>2020年06月24日 星期三 18:30</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> **题目描述：**
> 
> 现有一个机器要处理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内）。
> 
> **输出格式：**
> 
> 一行一个数，即最小惩罚因子和。
> 
> <table> 
>  <thead> 
>   <tr> 
>    <th>&nbsp;</th> 
>    <th>测试输入</th> 
>    <th>期待的输出</th> 
>    <th>时间限制</th> 
>    <th>内存限制</th> 
>    <th>额外进程</th> 
>   </tr> 
>  </thead> 
>  <tbody> 
>   <tr> 
>    <td>测试用例 1</td> 
>    <td>&nbsp; 
>     <ol> 
>      <li>3↵</li> 
>      <li>2&nbsp;2&nbsp;2↵</li> 
>      <li>6&nbsp;7&nbsp;8↵</li> 
>     </ol></td> 
>    <td>&nbsp; 
>     <ol> 
>      <li>6↵</li> 
>     </ol></td> 
>    <td>1秒</td> 
>    <td>64M</td> 
>    <td>0</td> 
>   </tr> 
>  </tbody> 
> </table>

--------------------

本题显然是贪心实现，具体怎么贪心呢！大概的思路就是：**优先考虑惩罚更重的任务，在考虑每一个任务的时候安排它在最靠近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\[ i \] = 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\n", 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

--------------------

# end  #

欢迎关注个人公众号**“** **鸡翅编程 ”**，这里是认真且乖巧的码农一枚。

*---- 做最乖巧的博客er，做最扎实的程序员 ----*

旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200111020715220.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw==,size_16,color_FFFFFF,t_70