PTA L2-043 龙龙送外卖

龙龙是“饱了呀”外卖软件的注册骑手,负责送帕特小区的外卖。帕特小区的构造非常特别,都是双向道路且没有构成环 —— 你可以简单地认为小区的路构成了一棵树,根结点是外卖站,树上的结点就是要送餐的地址。

每到中午 12 点,帕特小区就进入了点餐高峰。一开始,只有一两个地方点外卖,龙龙简单就送好了;但随着大数据的分析,龙龙被派了更多的单子,也就送得越来越累……

看着一大堆订单,龙龙想知道,从外卖站出发,访问所有点了外卖的地方至少一次(这样才能把外卖送到)所需的最短路程的距离到底是多少?每次新增一个点外卖的地址,他就想估算一遍整体工作量,这样他就可以搞明白新增一个地址给他带来了多少负担。

输入格式:

输入第一行是两个数 N 和 M (2≤N≤105, 1≤M≤105),分别对应树上节点的个数(包括外卖站),以及新增的送餐地址的个数。

接下来首先是一行 N 个数,第 i 个数表示第 i 个点的双亲节点的编号。节点编号从 1 到 N,外卖站的双亲编号定义为 −1。

接下来有 M 行,每行给出一个新增的送餐地点的编号 Xi​。保证送餐地点中不会有外卖站,但地点有可能会重复。

为了方便计算,我们可以假设龙龙一开始一个地址的外卖都不用送,两个相邻的地点之间的路径长度统一设为 1,且从外卖站出发可以访问到所有地点。

注意:所有送餐地址可以按任意顺序访问,且完成送餐后无需返回外卖站

输出格式:

对于每个新增的地点,在一行内输出题目需要求的最短路程的距离。

输入样例:

7 4
-1 1 1 1 2 2 3
5
6
2
4

输出样例:

2
4
4
6

做法:

首先你要明白 最短路程的距离 = 将给定点连通起来的最少边数 * 2 - 其中的最长边。

1.记录每一个节点的双亲节点

2.计算每个点到根节点的距离

3.计算所需边数 和 最长边

代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

//of记录双亲结点,visit是否访问过,gen到根节点的距离
int of[N],visit[N],gen[N];

int find(int x,int cnt)//cnt表示走了几步(经过了几条边),并求出到根节点的距离
{
    if(!visit[x]) 
    {
        visit[x] = 1;
        cnt = find(of[x],cnt + 1);
        gen[x] = gen[of[x]] + 1;
    }
    return cnt;
}
int main()
{
    int n = 0,m = 0;
    scanf("%d%d",&n,&m);
    //memset(gen,-1,sizeof(gen));
    for(int i = 1;i <= n;i++)
    {
        int t = 0;
        scanf("%d",&t);
        if(t == -1) visit[i] = 1,gen[i] = 0;//初始化根节点
        of[i] = t;//记录双亲节点
    }
    int len = 0,ma = 0;
    for(int i = 0;i < m;i++)
    {
        int t = 0;
        scanf("%d",&t);
        if(!visit[t]) len += find(t,0);//现在走了几条边
        if(ma < gen[t]) ma = gen[t];//求最长边
        printf("%d\n",len * 2 - ma);
    }
    return 0;
}

 将find函数分开写

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

//of记录双亲结点,visit是否访问过,gen到根节点的距离
int of[N],visit[N],gen[N];

int find(int x)
{
    if(gen[x] == -1) gen[x] = find(of[x]) + 1;
    return gen[x];
}
int main()
{
    int n = 0,m = 0;
    scanf("%d%d",&n,&m);
    memset(gen,-1,sizeof gen);

    for(int i = 1;i <= n;i++)
    {
        int t = 0;
        scanf("%d",&t);
        if(t == -1) gen[i] = 0,visit[i] = 1;
        of[i] = t;
    }
    int len = 0,ma = 0;
    for(int i = 0;i < m;i++)
    {
        int t = 0;
        scanf("%d",&t);
        if(ma < find(t)) ma = gen[t];//求最长边

        while(!visit[t])//求所 需边数 * 2
        {
            len += 2;//这里直接加2了
            visit[t] = 1;
            t = of[t];
        }
        printf("%d\n",len - ma);
    }
    return 0;
}

结果:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/506307.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Linux】权限理解

权限理解 1. shell命令以及运行原理2. Linux权限的概念3. Linux权限管理3.1 文件访问者的分类&#xff08;人&#xff09;3.2 文件类型和访问权限&#xff08;事物属性&#xff09;3.2.1 文件类型3.2.2 基本权限 3.3 文件权限值的表示方法3.4 文件访问权限的相关设置方法3.4.1 …

Taskflow应用:波前并行(Wavefront Parallelism)

2D的Wavefront如下图所示&#xff1a; #include <taskflow/taskflow.hpp>std::mutex cout_mutex; void format_str(std::string const& str) {std::lock_guard<std::mutex> lock(cout_mutex); std::cout << str << std::endl; }std::string crea…

算法编程:计算斐波那契数列

实现代码&#xff1a;C 实现方法&#xff1a;通过递推法、递归法、矩阵快速幂方法 适用&#xff1a; 范围小且单次查询时&#xff0c;可以不用记忆化处理。 范围大或多次查询时&#xff0c;应使用记忆化处理。 时间复杂度&#xff1a; 递归法&#xff1a;O(n^2)-->递推法(…

三台电机的顺启逆停

1&#xff0c;开启按钮输入信号是 电机一开始启动&#xff0c;5秒回电机2启动 &#xff0c;在5秒电机三启动 关闭按钮输入时电机3关闭 &#xff0c;5秒后电机2关闭 最后电机一关闭 2&#xff0c;思路开启按钮按下接通电机1 并且接通定时器T0 定时器T0 到时候接通电机2 并且开…

YOLOV8逐步分解(3)_trainer训练之模型加载

yolov8逐步分解(1)--默认参数&超参配置文件加载 yolov8逐步分解(2)_DetectionTrainer类初始化过程 接上2篇文章&#xff0c;继续讲解yolov8训练过程中的模型加载过程。 使用默认参数完成训练器trainer的初始化后&#xff0c;执行训练函数train()开始YOLOV8的训练。 1. t…

windows下安装iteliij Idea2023.3

首先从官网下载 双击打开进行安装&#xff1a; 安装完成后&#xff0c;需要对Idea进行稍微处理下。使用我分享给大家的文件&#xff0c;操作以下步骤&#xff1a; 注意&#xff1a;不能打开IDEA软件。 进入到scripts中点击uninstall-all-users.vbs,最后点击确定。 接下来运行in…

如何成功找到理想的工作,java不行了吗?我靠这个方法成功拿到大厂10个offer

第一段&#xff1a;引言 作为一名即将毕业的大学生&#xff0c;步入职场是每个毕业生都要面对的现实挑战。随着社会竞争的日益激烈&#xff0c;如何成功找到一份理想的工作成为许多毕业生所关注的焦点。本文将分享一些关于毕业生求职的经验和建议&#xff0c;希望能够帮助毕业生…

图的遍历试题

一、单项选择题 01.下列关于广度优先算法的说法中&#xff0c;正确的是( ). Ⅰ.当各边的权值相等时&#xff0c;广度优先算法可以解决单源最短路径问题 Ⅱ.当各边的权值不等时&#xff0c;广度优先算法可用来解决单源最短路径问题 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法…

C++中的动态内存管理

1.C中动态内存管理 C语言内存管理方式在C中可以继续使用&#xff0c;但有些地方就无能为力&#xff0c;而且使用起来比较麻烦&#xff0c;因此C又提出了自己的内存管理方式&#xff1a;通过new和delete操作符进行动态内存管理。 1.1 new/delete操作内置类型 c语言和c的动态内存…

Java_22 蓝桥杯真题——拼数

问题描述 给定几 个正整数 a1,a2....,an&#xff0c;你可以将它们任意排序, 现要将这 几 个数字连接成一排&#xff0c;即令相邻数字收尾相接&#xff0c;组成一个数。 问&#xff0c;这个数最大可以是多少。 输入格式 第一行输入个正整数 n(l < n< 20)。 第二行输入几 个…

Linux USB驱动(二)

1. Linux USB驱动软件框架 应用程序有两种访问硬件的途径&#xff1a;通过设备驱动程序来访问和跳过设备驱动程序&#xff08;直接使用host驱动程序&#xff09;来访问。 当直接使用Host驱动程序时&#xff0c;可以调用libusb库中已经封装好的函数接口。 2. USB电气信号 一个…

特征融合篇 | 利用RT-DETR的AIFI去替换YOLOv8中的SPPF(附2种改进方法)

前言:Hello大家好,我是小哥谈。RT-DETR模型是一种用于目标检测的深度学习模型,它基于transformer架构,特别适用于实时处理序列数据。在RT-DETR模型中,AIFI(基于注意力的内部尺度特征交互)模块是一个关键组件,它通过引入注意力机制来增强模型对局部和全局信息的处理能力…

2024全开源小狐狸ai付费创作系统V2.8.0

源码介绍 小狐狸GPT付费体验系统的开发基于国外很火的ChatGPT&#xff0c;这是一种基于人工智能技术的问答系统&#xff0c;可以实现智能回答用户提出的问题。相比传统的问答系统&#xff0c;ChatGPT可以更加准确地理解用户的意图&#xff0c;提供更加精准的答案。同时&#x…

从0开始搭建基于VUE的前端项目(三) Vuex的使用与配置

准备与版本 vuex 3.6.2(https://v3.vuex.vuejs.org/zh/)概念 vuex是什么? 是用作 【状态管理】的 流程图如下 state 数据状态,成员是个对象 mapState 组件使用this.$store.state.xxx获取state里面的数据 getters 成员是个函数,方便获取state里面的数据,也可以加工数据 ma…

HarmonyOS 应用开发之组件启动规则(Stage模型)

启动组件是指一切启动或连接应用组件的行为&#xff1a; 启动UIAbility、ServiceExtensionAbility、DataShareExtensionAbility&#xff0c;如使用startAbility()、startServiceExtensionAbility()、startAbilityByCall()等相关接口。 连接ServiceExtensionAbility、DataShare…

[BT]BUUCTF刷题第12天(3.31)

第12天 Basic BUU BURP COURSE 1 经过尝试&#xff0c;在这里X-Forwarded-For不管用&#xff0c;要用X-Real-IP BP抓包添加X-Real-IP:127.0.0.1&#xff08;注意这一行前面不要有空行&#xff09; 发送后返回提示了用户名和密码&#xff0c;这里直接给了&#xff0c;登录即可…

unity学习(78)--unity调试--长痛不如短痛

1.在vs2022中&#xff0c;工具--获取工具与功能。 2. 安装图中工具&#xff0c;原来我早就安装了。 3 f9下断 同时点击图中按钮 vs此时变为如下状态 unity中出现如下提示&#xff1a; 4 在unity中运行游戏&#xff0c;vs这边确实成功断住了&#xff01;

【千帆杯】K12教育常规赛 北京场线下交流会心得

千帆杯K12教育常规赛 北京场线下交流会心得 ​ 周日有幸参加了 百度智能云千帆AppBuilder北京场线下交流会 ( 活动链接 )&#xff0c;去线下组队创作了 K12教育 相关的智能体。参赛过程中认识了不少大佬与朋友&#xff0c;抱大佬队友的腿&#xff0c;他的 猜成语 应用获得了线…

【详细讲解WebView的使用与后退键处理】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

前端三剑客 —— CSS (第二节)

目录 内容回顾&#xff1a; CSS选择器*** 属性选择器 伪类选择器 1&#xff09;:link 超链接点击之前 2&#xff09;:visited 超链接点击之后 3&#xff09;:hover 鼠标悬停在某个标签上时 4&#xff09;:active 鼠标点击某个标签时&#xff0c;但没有松开 5&#xff09;:fo…