CCF-CSP真题《202212-2 训练计划》思路+python，c++满分题解

川长思鸟来 2023-09-27 14:36 105阅读 0赞

> 想查看其他题的真题及题解的同学可以前往查看：[CCF-CSP真题附题解大全][CCF-CSP]

<table> 
 <tbody> 
  <tr> 
   <td>试题编号：</td> 
   <td>202212-2</td> 
  </tr> 
  <tr> 
   <td>试题名称：</td> 
   <td>训练计划</td> 
  </tr> 
  <tr> 
   <td>时间限制：</td> 
   <td>1.0s</td> 
  </tr> 
  <tr> 
   <td>内存限制：</td> 
   <td>512.0MB</td> 
  </tr> 
  <tr> 
   <td>问题描述：</td> 
   <td> <h3>问题背景</h3> <p>西西艾弗岛荒野求生大赛还有&nbsp;n&nbsp;天开幕！</p> <h3>问题描述</h3> <p>为了在大赛中取得好成绩，顿顿准备在&nbsp;n&nbsp;天时间内完成“短跑”、“高中物理”以及“核裂变技术”等总共&nbsp;m&nbsp;项科目的加强训练。其中第&nbsp;i&nbsp;项（1≤i≤m）科目编号为&nbsp;i，也可简称为科目&nbsp;i。已知科目&nbsp;i&nbsp;耗时&nbsp;ti&nbsp;天，即如果从第&nbsp;a&nbsp;天开始训练科目&nbsp;i，那么第&nbsp;a+ti−1&nbsp;天就是该项训练的最后一天。</p> <p>大部分科目的训练可以同时进行，即顿顿在同一天内可以同时进行多项科目的训练，但部分科目之间也存在着依赖关系。如果科目&nbsp;i&nbsp;依赖科目&nbsp;j，那么只能在后者训练结束后，科目&nbsp;i&nbsp;才能开始训练。具体来说，如果科目&nbsp;j&nbsp;从第&nbsp;a&nbsp;天训练到第&nbsp;a+tj−1&nbsp;天，那么科目&nbsp;i&nbsp;最早只能从第&nbsp;a+tj&nbsp;天开始训练。还好，顿顿需要训练的&nbsp;m&nbsp;项科目依赖关系并不复杂，每项科目最多只依赖一项别的科目，且满足依赖科目的编号小于自己。那些没有任何依赖的科目，则可以从第&nbsp;1&nbsp;天就开始训练。</p> <p>对于每一项科目，试计算：</p> <p>1）最早开始时间：该科目最早可以于哪一天开始训练？</p> <p>2）最晚开始时间：在不耽误参赛的前提下（n&nbsp;天内完成所有训练），该科目最晚可以从哪一天开始训练？</p> <p>n&nbsp;天内完成所有训练，即每一项科目训练的最后一天都要满足&nbsp;≤n。需要注意，顿顿如果不能在&nbsp;n&nbsp;天内完成全部&nbsp;m&nbsp;项科目的训练，就无法参加大赛。这种情况下也就不需要再计算“最晚开始时间”了。</p> <h3>输入格式</h3> <p>从标准输入读入数据。</p> <p>输入共三行。</p> <p>输入的第一行包含空格分隔的两个正整数&nbsp;n&nbsp;和&nbsp;m，分别表示距离大赛开幕的天数和训练科目的数量。</p> <p>输入的第二行包含空格分隔的&nbsp;m&nbsp;个整数，其中第&nbsp;i&nbsp;个（1≤i≤m）整数&nbsp;pi&nbsp;表示科目&nbsp;i&nbsp;依赖的科目编号，满足&nbsp;0≤pi&lt;i；pi=0&nbsp;表示科目&nbsp;i&nbsp;无依赖。</p> <p>输入的第三行包含空格分隔的&nbsp;m&nbsp;个正整数，其中第&nbsp;i&nbsp;个（1≤i≤m）数&nbsp;ti&nbsp;表示训练科目&nbsp;i&nbsp;所需天数，满足&nbsp;1≤ti≤n。</p> <h3>输出格式</h3> <p>输出到标准输出中。</p> <p>输出共一行或两行。</p> <p>输出的第一行包含空格分隔的&nbsp;m&nbsp;个正整数，依次表示每项科目的最早开始时间。</p> <p>如果顿顿可以在&nbsp;n&nbsp;天内完成全部&nbsp;m&nbsp;项科目的训练，则继续输出第二行，否则输出到此为止。</p> <p>输出的第二行包含空格分隔的&nbsp;m&nbsp;个正整数，依次表示每项科目的最晚开始时间。</p> <h3>样例 1 输入</h3> 
    <blockquote> 
     <p>10 5<br> 0 0 0 0 0<br> 1 2 3 2 10</p> 
    </blockquote> <h3>样例 1 输出</h3> 
    <blockquote> 
     <p>1 1 1 1 1<br> 10 9 8 9 1</p> 
    </blockquote> <h3>样例 1 说明</h3> <p>五项科目间没有依赖关系，都可以从第&nbsp;1&nbsp;天就开始训练。</p> <p>10&nbsp;天时间恰好可以完成所有科目的训练。其中科目&nbsp;1&nbsp;耗时仅&nbsp;1&nbsp;天，所以最晚可以拖延到第&nbsp;10&nbsp;天再开始训练；而科目&nbsp;5&nbsp;耗时&nbsp;10&nbsp;天，必须从第&nbsp;1&nbsp;天就开始训练。</p> <h3>样例 2 输入</h3> 
    <blockquote> 
     <p>10 7<br> 0 1 0 3 2 3 0<br> 2 1 6 3 10 4 3</p> 
    </blockquote> <h3>样例 2 输出</h3> 
    <blockquote> 
     <p>1 3 1 7 4 7 1</p> 
    </blockquote> <h3>样例 2 说明</h3> <p>七项科目间的依赖关系如图所示，其中仅科目&nbsp;5&nbsp;无法在&nbsp;10&nbsp;天内完成训练。</p> <p><img alt="" height="169" src="https://img-blog.csdnimg.cn/a718c19677c144f196329091812764b0.png" width="755"></p> <p></p> <p>具体来说，科目&nbsp;5&nbsp;依赖科目&nbsp;2、科目&nbsp;2&nbsp;又依赖于科目&nbsp;1，因此科目&nbsp;5&nbsp;最早可以从第&nbsp;4&nbsp;天开始训练。</p> <h3>样例 3 输入</h3> 
    <blockquote> 
     <p>10 5<br> 0 1 2 3 4<br> 10 10 10 10 10</p> 
    </blockquote> <h3>样例 3 输出</h3> 
    <blockquote> 
     <p>1 11 21 31 41</p> 
    </blockquote> <h3>子任务</h3> <p>70&nbsp;的测试数据满足：顿顿无法在&nbsp;n&nbsp;天内完成全部&nbsp;m&nbsp;项科目的训练，此时仅需输出一行“最早开始时间”；</p> <p>全部的测试数据满足&nbsp;0&lt;n≤365&nbsp;且&nbsp;0&lt;m≤100。</p> </td> 
  </tr> 
 </tbody> 
</table>

**真题来源：**[训练计划][Link 1]

> 感兴趣的同学可以如此编码进去进行练习提交

**直接无脑解(70分)：**

**运行结果：**

![4e4b1e17ca8c4cfa8ea22ab639e7422d.png][]

**错误解析：**

> 这种解法属于第二题看到题直白写就好，由于70% 的测试数据满足：顿顿无法在 n 天内完成全部 m 项科目的训练，此时不需要考虑最晚开始时间是否输出的问题，这是不符题意的，但也有70分入手。

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

**pyhon满分题解：**

n, m = map(int,input().split())
    p = [0]+[i for i in map(int,input().split())]
    t = [0]+[i for i in map(int,input().split())]
    earliest = [0 for _ in range(m+1)]
    latest = [0 for _ in range(m+1)]
    mark = 1
    # 将每个科目的最早时间确定
    for i in range(1,m+1):
        if p[i]==0:
            earliest[i] = 1
        else:
            earliest[i] = earliest[p[i]]+t[p[i]]
        # 判断所有科目最早开始的情况是否可以完成所有科目
        if earliest[i]+t[i]-1>n:
            mark = 0
    # 输出每项科目的最早开始时间
    print(*earliest[1:])
    
    # 判断是否可以完成项目
    if mark==1:
        # 将确定每个科目的最晚，从最后的科目往前推，需要把依赖该科目的科目所消耗时间算上
        for i in range(m, 0, -1):
            temp = 366
            for j in range(i+1, m+1):
                #寻找是否有依赖该科目的科目
                if p[j] == i:
                    temp = min(temp, latest[j])
            #如果没有被依赖，那么最晚开始时间 = 最后期限 - 持续时间的时刻
            if temp == 366:
                latest[i] = n-t[i]+1
            #如果有被依赖，那么最晚开始时间 = 依赖它的科目的最晚开始的时刻最小的科目 - 本身的持续时间的时刻
            else:
                latest[i] = temp-t[i]
        # 输出每项科目的最早开始时间
        print(*latest[1:])

**运行结果：**

![20af132cee7f400b9944641aaa2157e4.png][]

**思路解析：**

> 在最早开始时间的计算中，每一个科目的最早开始时间依赖于它的前继科目；
> 
> 而在最晚开始时间的计算中，由于某科目是被别的科目依赖的，所以计算它的最晚开始时间时要考虑依赖它的科目能否如期完成，所以我们做个标记 mark ，如果最早可以完成，则继续分析最晚开始时间；
> 
> 而将确定每个科目的最晚，需要从最后的科目往前推，因为如果有依赖的科目，需要把依赖该科目的科目所消耗时间算上，如果没有被依赖，那么最晚开始时间 = 最后期限 - 持续时间的时刻，如果有被依赖，那么最晚开始时间 = 依赖它的科目的最晚开始的时刻最小的科目 - 本身的持续时间的时刻。

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

**c++满分题解：**

#include<iostream>
    #include<cmath>
    using namespace std;
    
    const int N = 101;
    int n, m;
    int p[N], t[N];
    int earliest[N], latest[N];
    
    int main() {
        int mark = 1;
        cin >> n >> m;
        for (int i = 1; i <= m; i++) 
            cin >> p[i];
        for (int i = 1; i <= m; i++) 
            cin >> t[i];
        // 将每个科目的最早时间确定
        for (int i = 1; i <= m; i++) {
            if (p[i] == 0)
                earliest[i] = 1;
            else
                earliest[i] = earliest[p[i]] + t[p[i]];
            // 判断所有科目最早开始的情况是否可以完成所有科目
            if (earliest[i] + t[i] - 1 > n)
                mark = 0;
        }
        // 输出每项科目的最早开始时间
        for (int i = 1; i <= m; i++)
            cout << earliest[i] << " ";
        cout << endl;
        // 判断是否可以完成项目
        if (mark == 1) {
            // 将确定每个科目的最晚，从最后的科目往前推，需要把依赖该科目的科目所消耗时间算上
            for (int i = m; i >= 1; i--) {
                int temp = 366;
                for (int j = i + 1; j <= m; j++) {
                    // 寻找是否有依赖该科目的科目
                    if (p[j] == i)
                        temp = min(temp, latest[j]);
                } 
                // 如果没有被依赖，那么最晚开始时间 = 最后期限 - 持续时间的时刻
                if (temp == 366)
                    latest[i] = n - t[i] + 1;
                // 如果有被依赖，那么最晚开始时间 = 依赖它的科目的最晚开始的时刻最小的科目 - 本身的持续时间的时刻
                else
                    latest[i] = temp - t[i];
            }
            // 输出每项科目的最晚开始时间
            for (int i = 1; i <= m; i++)
                cout << latest[i] << " ";
        }
        return 0;
    }

**运行结果：**

![1a58c674a065419a8aa3009d32e4516a.png][]

[CCF-CSP]: https://blog.csdn.net/weixin_53919192/article/details/124893395?spm=1001.2014.3001.5502
[Link 1]: http://118.190.20.162/view.page?gpid=T159
[4e4b1e17ca8c4cfa8ea22ab639e7422d.png]: https://img-blog.csdnimg.cn/4e4b1e17ca8c4cfa8ea22ab639e7422d.png
[20af132cee7f400b9944641aaa2157e4.png]: https://img-blog.csdnimg.cn/20af132cee7f400b9944641aaa2157e4.png
[1a58c674a065419a8aa3009d32e4516a.png]: https://img-blog.csdnimg.cn/1a58c674a065419a8aa3009d32e4516a.png