【CF】1422D-Returning Home 题解

2024-08-27 13:52
文章标签 题解 cf home returning 1422d

本文主要是介绍【CF】1422D-Returning Home 题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门:1422D
标签:贪心

题目大意

Yura 已经走了很长时间,他计划尽快回家。为了做到这一点,Yura 可以利用城市周围的瞬间移动地点。把城市看作是一个 n × n n × n n×n 方形街区。Yura 需要从坐标 ( s x , s y ) (s_x, s_y) (sx,sy) 的街区移动到坐标 ( f x , f y ) (f_x, f_y) (fx,fy) 的街区。在一分钟内,Yura 可以移动到相邻的街区;换句话说,他可以在四个方向上移动。此外,城市中有 m m m 个瞬间移动地点。他们的坐标已知并告诉 Yura。如果 Yura 所在的街区与瞬间移动地点的坐标相同,他可以在不花费时间的情况下移动到瞬间移动地点。帮助 Yura 找出回家所需的最短时间。

输入:第一行包含两个整数 n n n m m m — 城市的大小和瞬间移动地点的数量( 1 ≤ n ≤ 1 0 9 1 ≤ n ≤ 10^9 1n109, 0 ≤ m ≤ 1 0 5 0 ≤ m ≤ 10^5 0m105)。下一行包含四个整数 s x , s y , f x , f y s_x, s_y, f_x, f_y sx,sy,fx,fy — Yura 的初始位置坐标和他的家的坐标( 1 ≤ s x , s y , f x , f y ≤ n 1 ≤ s_x, s_y, f_x, f_y ≤ n 1sx,sy,fx,fyn)。接下来的 m m m 行各包含两个整数 x i , y i x_i, y_i xi,yi — 第 i i i 个瞬间移动地点的坐标( 1 ≤ x i , y i ≤ n 1 ≤ x_i, y_i ≤ n 1xi,yin)。
输出:在唯一行中输出返回所需的时间。

算法分析

很显然,当 K = 2 K = 2 K=2 时,我们可以从任何原子 i i i 1 ≤ i < N 1 ≤ i < N 1i<N)开始制作激发路线来激发所有原子。因此,对于 K > 2 K > 2 K>2,我们可以通过切换键来制作路线。因此,有三种情况:
如果 K = 0 K = 0 K=0,最优选择是只激发一个原子。尝试激发每个原子 i i i 并使用前缀和计算获得的能量。
如果 K ≥ 2 K ≥ 2 K2,我们可以选择激发一个原子 i i i 1 ≤ i < N 1 ≤ i < N 1i<N),这会激发所有原子,或者仅激发最后一个原子(如果 D D D 最低的话)。
如果 K = 1 K = 1 K=1 ,需要分情况讨论,共有五种情况:

  1. E N − 1 E_{N - 1} EN1 改变为 1。然后激发 D i D_i Di 1 ≤ i < N 1 ≤ i < N 1i<N 的原子。同时,如果能量增加,则激发原子 N N N
  2. E i E_i Ei 改变为 1 然后激发原子 i i i i + 1 i + 1 i+1 1 < i < N 1 < i < N 1<i<N)。激发 i + 1 i + 1 i+1 是最优的,因为如果不这样做,情况会比情况 1 更糟。
  3. E 1 E_1 E1 改变为 3,然后激发 1 和 2。
  4. E 1 E_1 E1 改变为 N N N,然后激发原子 i i i 1 < i ≤ N 1 < i ≤ N 1<iN
  5. E i E_i Ei 改变为 i + 2 i + 2 i+2,然后激发原子 1( 1 < i < N 1 < i < N 1<i<N)。只有当我们激发原子 1 时,这是最优的,否则它比情况 4 更差。

总体时间复杂度: O ( N ) O(N) O(N)

代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e6+10;
struct node
{int x,y,id;
}f[N];
struct node1
{int to,w,next;
}e[N];
int cnt,head[N];
int dist[N],vis[N];
int n,m;
void add(int x,int y,int z)
{cnt++;e[cnt].to=y;e[cnt].w=z;e[cnt].next=head[x];head[x]=cnt;
}
bool cmp1(node a,node b)
{return a.x<b.x;
}
bool cmp2(node a,node b)
{return a.y<b.y; 
}
void dij()
{memset(dist,0x3f,sizeof dist);dist[m+1]=0;priority_queue<pair<int,int> > q;q.push({0,m+1});while(q.size()){auto p=q.top();q.pop();int xx=p.second;if(vis[xx]) continue;vis[xx]=1;for(int i=head[xx];i;i=e[i].next){int yy=e[i].to;if(dist[yy]>dist[xx]+e[i].w){dist[yy]=dist[xx]+e[i].w;q.push({-dist[yy],yy});}}}
}
signed main()
{cin>>n>>m;int sx,sy,ex,ey;cin>>sx>>sy>>ex>>ey;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;f[i].x=x,f[i].y=y,f[i].id=i;add(m+1,i,min(abs(x-sx),abs(y-sy)));add(i,m+1,min(abs(x-sx),abs(y-sy)));add(m+2,i,abs(x-ex)+abs(y-ey));add(i,m+2,abs(x-ex)+abs(y-ey));}add(m+1,m+2,abs(sx-ex)+abs(sy-ey));add(m+2,m+1,abs(sx-ex)+abs(sy-ey));sort(f+1,f+m+1,cmp1);for(int i=2;i<=m;i++){int id1=f[i-1].id,id2=f[i].id;int w=min(abs(f[i].x-f[i-1].x),abs(f[i].y-f[i-1].y));add(id1,id2,w);add(id2,id1,w);}sort(f+1,f+m+1,cmp2);for(int i=2;i<=m;i++){int id1=f[i-1].id,id2=f[i].id;int w=min(abs(f[i].x-f[i-1].x),abs(f[i].y-f[i-1].y));add(id1,id2,w);add(id2,id1,w);}dij();cout<<dist[m+2]<<'\n';
}

这篇关于【CF】1422D-Returning Home 题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1111850

相关文章

【IPV6从入门到起飞】5-1 IPV6+Home Assistant(搭建基本环境)

【IPV6从入门到起飞】5-1 IPV6+Home Assistant #搭建基本环境 1 背景2 docker下载 hass3 创建容器4 浏览器访问 hass5 手机APP远程访问hass6 更多玩法 1 背景 既然电脑可以IPV6入站,手机流量可以访问IPV6网络的服务,为什么不在电脑搭建Home Assistant(hass),来控制你的设备呢?@智能家居 @万物互联

cf 164 C 费用流

给你n个任务,k个机器,n个任务的起始时间,持续时间,完成任务的获利 每个机器可以完成任何一项任务,但是同一时刻只能完成一项任务,一旦某台机器在完成某项任务时,直到任务结束,这台机器都不能去做其他任务 最后问你当获利最大时,应该安排那些机器工作,即输出方案 具体建图方法: 新建源汇S T‘ 对任务按照起始时间s按升序排序 拆点: u 向 u'连一条边 容量为 1 费用为 -c,

CF 508C

点击打开链接 import java.util.Arrays;import java.util.Scanner;public class Main {public static void main(String [] args){new Solve().run() ;} }class Solve{int bit[] = new int[608] ;int l

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

log4j2相关配置说明以及${sys:catalina.home}应用

${sys:catalina.home} 等价于 System.getProperty("catalina.home") 就是Tomcat的根目录:  C:\apache-tomcat-7.0.77 <PatternLayout pattern="%d{yyyy-MM-dd HH:mm:ss} [%t] %-5p %c{1}:%L - %msg%n" /> 2017-08-10

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析

Vue2电商项目(二) Home模块的开发;(还需要补充js节流和防抖的回顾链接)

文章目录 一、Home模块拆分1. 三级联动组件TypeNav2. 其余组件 二、发送请求的准备工作1. axios的二次封装2. 统一管理接口API----跨域3. nprogress进度条 三、 vuex模块开发四、TypeNav三级联动组件开发1. 动态展示三级联动数据2. 三级联动 动态背景(1)、方式一:CSS样式(2)、方式二:JS 3. 控制二三级数据隐藏与显示--绑定styl