CCF刷题计划——训练计划(反向拓扑排序)

news/2025/1/15 21:45:00/

训练计划

计算机软件能力认证考试系统

这道题70分还是很好拿的。后面30分需要用到 反向拓扑排序 ,相对而言就麻烦点,需要逆序遍历。不着急,我们慢慢来。首先给出70分的代码。

本题可以学到:反向拓扑排序

70分题解:

#include <iostream>
#include <vector>
using namespace std;
const int N=366;
//如果只考虑70%,都不能满足,被依赖者越早发生越好。
//剩下的30%,应该是无依赖,和依赖也能完成,被依赖者可以适当延后
//我们可以先按照越早发生的情况把相应的算出来,并记录好这条链。然后从最晚发生的开始,向上增加天数。
//但是问题在于,这只能改这一条上的数据。如果有链和其相交,交点位置改变,会影响支链的情况。
//好吧,那就先只弄70分的吧 int n,m;	//距离大赛开幕的天数 训练科目的数量
vector<int>depend(N);	//依赖情况 
vector<int>cost(N);	//消耗天数 int main()
{cin>>n>>m; for(int i=1;i<=m;i++)	cin>>depend[i];for(int i=1;i<=m;i++)	cin>>cost[i];for(int i=1;i<=m;i++){if(depend[i]==0)	cout<<1<<" ";else{int t=depend[i];int sum=0;while(t!=0){sum+=cost[t];t=depend[t];} cout<<1+sum<<" ";}}return 0;
}

计算最晚开始时间latest 数组)的逻辑是基于课程的依赖关系,通过反向遍历所有课程来实现的。这种方法通常称为“反向拓扑排序”或“逆后序遍历”,因为它从没有任何依赖(即出度为0)的课程开始,然后逐步向前追溯到有依赖关系的课程。

  1. 初始化

    • 对于所有课程,最晚开始时间(latest 数组)的初始值可以设置为一个足够大的数(比如INT_MAX),但在这个代码中,由于已经知道总时间限制为n天,并且每个课程都需要一定的时间来完成,所以更合理的初始化方式是针对没有依赖的课程(即入度为0的课程),将其最晚开始时间设置为n - cost[i] + 1,这里cost[i]是课程i所需的训练天数。

  2. 反向遍历

    m(最后一个课程的编号)开始,递减遍历到1(第一个课程的编号)。

    对于每个课程i

    • 如果课程i没有依赖(即mp[i].size() == 0),则直接根据总时间限制和该课程的训练天数来设置其最晚开始时间:latest[i] = n - cost[i] + 1。这是因为没有任何课程依赖于课程i,所以课程i可以在不迟于n - cost[i] + 1天开始,以确保在n天内完成。

    • 如果课程i有依赖(即mp[i].size() > 0),则需要找到所有依赖于课程i的课程(即mp[i]中的课程)的最晚开始时间中的最小值,然后从这个最小值中减去课程i的训练天数来得到课程i的最晚开始时间。这是因为课程i必须在其所有依赖课程之后开始,以确保在它们完成之后才能开始课程i我在代码中举了例子,大家可以看看。

  3. 计算过程

    • 在计算过程中,由于是从后向前遍历,所以当一个课程的最晚开始时间被计算出来时,它的所有依赖课程的最晚开始时间都已经被计算过了。这使得我们能够正确地找到依赖课程中的最晚开始时间的最小值。

    AC:

#include <iostream>
#include <map>
#include <vector>
using namespace std;int n,m;
map<int,vector<int>>mp;			// <科目i,<依赖于i的科目集合>> 
bool f=false;					//判断是否能在规定时间内训练完 int main()
{cin >>n>>m;vector<int> depend(m + 1);		//科目i所依赖的科目depend[i]vector<int> cost(m + 1);		//科目i所需的训练天数	vector<int> earlist(m + 1);		//科目i最早开始时间vector<int> latest(m + 1);		//科目i最晚开始时间for (int i = 1; i <= m; i++) {cin >> depend[i];mp[depend[i]].push_back(i);}for (int i = 1; i <= m; i++)	cin >> cost[i];for (int i = 1; i <= m; i++) {if (depend[i] == 0)earlist[i] = 1;else {int k = depend[i];earlist[i] = earlist[k] + cost[k];if (earlist[i] + cost[i] > n)f = true;	//表示不能在规定时间内做完}cout << earlist[i] << " ";}if (f) 	//不能做完,那就到此为止 return 0;//能在规定时间内做完,继续输出最晚开始时间 cout<<endl;for (int i = m; i >= 1; i--) {if (mp[i].size() == 0) latest[i] = n - cost[i] + 1;else {int min_num = latest[mp[i][0]];	
//所有依赖课程的最晚开始时间中的最小值,也就是最先完成的依赖课程for (int j = 0; j < mp[i].size(); j++) {if (latest[mp[i][j]] < min_num)min_num = latest[mp[i][j]];}latest[i] = min_num - cost[i];	/*当前课程的最晚开始时间不是由他决定的,而是由他的依赖课程决定的。
后续依赖课程都满足贴屁股完成,在此前提下,越早开始的,其最晚开始时间越小。
我们就是要满足这个最小时间,才能确定当前课程i的最晚开始时间。比如有2、3都依赖1。现在我们想确定1的最晚开始时间。
已知2的最晚开始时间是5,到10结束;3的最晚开始时间是7,到10结束;cost[1]=1。
按照上述方法,我们应该选择5作为min_num,然后计算latest[1]=5-cost[1]=4,作为1的最晚开始时间。
如果我们选择7,latest[1]=7-cost[1]=6。
然后我们发现,2的最晚开始时间是5,1的最晚开始时间是6,但是2又依赖于1,1本应该比2先开始。
所以出现矛盾。*/}}for (int i = 1; i <= m; i++)	cout << latest[i] << " ";	return 0;
}

参考代码:【CCF CSP】202212-2 训练计划-CSDN博客


http://www.ppmy.cn/news/1525590.html

相关文章

红黑树的删除

文章目录 前言一.删除的节点左子树右子树都有二.删除的节点只有左/右子树删除调整操作 三.删除的节点没有孩子1.删除的节点为红色2.删除的节点为黑色1).兄弟节点为黑色(1).兄弟节点至少有一个红色的孩子节点LL型RR型RL型LR型 (2).兄弟节点没有孩子或所有孩子为黑色 2).兄弟节点…

【贪心算法】贪心算法

贪心算法简介 1.什么是贪心算法2.贪心算法的特点3.学习贪心的方向 点赞&#x1f44d;&#x1f44d;收藏&#x1f31f;&#x1f31f;关注&#x1f496;&#x1f496; 你的支持是对我最大的鼓励&#xff0c;我们一起努力吧!&#x1f603;&#x1f603; 1.什么是贪心算法 与其说是…

跨系统环境下LabVIEW程序稳定运行

在LabVIEW开发中&#xff0c;不同电脑的配置和操作系统&#xff08;如Win11与Win7&#xff09;可能对程序的稳定运行产生影响。为了确保程序在不同平台上都能正常且稳定运行&#xff0c;需要从兼容性、驱动、以及性能优化等多个方面入手。本文将详细介绍如何在不同系统环境下&a…

Integer 缓存

在 Java 中&#xff0c;如果你通过 new Integer(value) 显式创建一个 Integer 对象&#xff0c;以下几点需要注意&#xff1a; 内存中的 Integer 对象 缓存范围&#xff1a; Java 自动缓存的 Integer 对象范围是从 -128 到 127。这些对象在类加载时被创建并存储在内存中。 使…

服务网关工作原理,如何获取用户真实IP?

文章目录 一、什么是网关二、网关工作原理 (★)三、SpringCloud Gateway3.1 Gateway 简介3.2 Gateway 环境搭建3.3 自定义路由规则 (★)3.4 局部过滤器3.5 全局过滤器&#xff08;案例&#xff1a;获取用户真实IP地址&#xff09; (★) 补充1&#xff1a;不同类型的客户端如何设…

使用@test-library/react的screen中的方法和直接使用getByText,getByTestId等的区别?

在 React Testing Library 中&#xff0c;screen 对象和直接使用 getByText, getByTestId 等方法之间的主要区别在于它们的使用方式和上下文。然而&#xff0c;从功能的角度来看&#xff0c;它们实际上是相互关联的&#xff0c;因为 screen 对象提供了一组封装好的查询方法&…

2024非常全的接口测试面试题及参考答案

一、前言 接口测试最近几年被炒的火热了&#xff0c;越来越多的测试同行意识到接口测试的重要性。接口测试为什么会如此重要呢&#xff1f; 主要是平常的功能点点点&#xff0c;大家水平都一样&#xff0c;是个人都能点&#xff0c;面试时候如果问你平常在公司怎么测试的&…

11Python的Pandas:可视化

Pandas本身并没有直接的可视化功能&#xff0c;但它与其他Python库&#xff08;如Matplotlib和Seaborn&#xff09;无缝集成&#xff0c;允许你快速创建各种图表和可视化。这里是一些使用Pandas数据进行可视化的常见方法&#xff1a; 1. 使用Matplotlib Pandas中的plot()方法…