当前位置: 首页 > news >正文

[NOIP2012 提高组] 开车旅行

[NOIP2012 提高组] 开车旅行

题目描述

A \text{A} A 和小 B \text{B} B 决定利用假期外出旅行,他们将想去的城市从 $1 $ 到 n n n 编号,且编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同,记城市 i i i 的海拔高度为 h i h_i hi,城市 i i i 和城市 j j j 之间的距离 d i , j d_{i,j} di,j 恰好是这两个城市海拔高度之差的绝对值,即 d i , j = ∣ h i − h j ∣ d_{i,j}=|h_i-h_j| di,j=hihj

旅行过程中,小 A \text{A} A 和小 B \text{B} B 轮流开车,第一天小 A \text{A} A 开车,之后每天轮换一次。他们计划选择一个城市 s s s 作为起点,一直向东行驶,并且最多行驶 x x x 公里就结束旅行。

A \text{A} A 和小 B \text{B} B 的驾驶风格不同,小 B \text{B} B 总是沿着前进方向选择一个最近的城市作为目的地,而小 A \text{A} A 总是沿着前进方向选择第二近的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的那个城市更近)。如果其中任何一人无法按照自己的原则选择目的城市,或者到达目的地会使行驶的总距离超出 x x x 公里,他们就会结束旅行。

在启程之前,小 A \text{A} A 想知道两个问题:

1、 对于一个给定的 x = x 0 x=x_0 x=x0,从哪一个城市出发,小 A \text{A} A 开车行驶的路程总数与小 B \text{B} B 行驶的路程总数的比值最小(如果小 B \text{B} B 的行驶路程为 0 0 0,此时的比值可视为无穷大,且两个无穷大视为相等)。如果从多个城市出发,小 A \text{A} A 开车行驶的路程总数与小 B \text{B} B 行驶的路程总数的比值都最小,则输出海拔最高的那个城市。

2、对任意给定的 x = x i x=x_i x=xi 和出发城市 s i s_i si,小 A \text{A} A 开车行驶的路程总数以及小 B \text B B 行驶的路程总数。

输入格式

第一行包含一个整数 n n n,表示城市的数目。

第二行有 n n n 个整数,每两个整数之间用一个空格隔开,依次表示城市 1 1 1 到城市 n n n 的海拔高度,即 h 1 , h 2 . . . h n h_1,h_2 ... h_n h1,h2...hn,且每个 h i h_i hi 都是互不相同的。

第三行包含一个整数 x 0 x_0 x0

第四行为一个整数 m m m,表示给定 m m m s i s_i si x i x_i xi

接下来的 m m m 行,每行包含 2 2 2 个整数 s i s_i si x i x_i xi,表示从城市 s i s_i si 出发,最多行驶 x i x_i xi 公里。

输出格式

输出共 m + 1 m+1 m+1 行。

第一行包含一个整数 s 0 s_0 s0,表示对于给定的 x 0 x_0 x0,从编号为 s 0 s_0 s0 的城市出发,小 A \text A A 开车行驶的路程总数与小 B \text B B 行驶的路程总数的比值最小。

接下来的 m m m 行,每行包含 2 2 2 个整数,之间用一个空格隔开,依次表示在给定的 s i s_i si x i x_i xi 下小 A \text A A 行驶的里程总数和小 B \text B B 行驶的里程总数。

样例 #1

样例输入 #1

4 
2 3 1 4 
3 
4 
1 3 
2 3 
3 3 
4 3

样例输出 #1

1 
1 1 
2 0 
0 0 
0 0

样例 #2

样例输入 #2

10 
4 5 6 1 2 3 7 8 9 10 
7 
10 
1 7 
2 7 
3 7 
4 7 
5 7 
6 7 
7 7 
8 7 
9 7 
10 7

样例输出 #2

2 
3 2 
2 4 
2 1 
2 4 
5 1 
5 1 
2 1 
2 0 
0 0 
0 0

提示

【样例1说明】

各个城市的海拔高度以及两个城市间的距离如上图所示。

如果从城市 1 1 1 出发,可以到达的城市为 2 , 3 , 4 2,3,4 2,3,4,这几个城市与城市 1 1 1 的距离分别为 1 , 1 , 2 1,1,2 1,1,2,但是由于城市 3 3 3 的海拔高度低于城市 2 2 2,所以我们认为城市 3 3 3 离城市 1 1 1 最近,城市 2 2 2 离城市 1 1 1 第二近,所以小A会走到城市 2 2 2。到达城市 2 2 2 后,前面可以到达的城市为 3 , 4 3,4 3,4,这两个城市与城市 2 2 2 的距离分别为 2 , 1 2,1 2,1,所以城市 4 4 4 离城市 2 2 2 最近,因此小B会走到城市 4 4 4。到达城市 4 4 4 后,前面已没有可到达的城市,所以旅行结束。

如果从城市 2 2 2 出发,可以到达的城市为 3 , 4 3,4 3,4,这两个城市与城市 2 2 2 的距离分别为 2 , 1 2,1 2,1,由于城市 3 3 3 离城市 2 2 2 第二近,所以小 A \text A A 会走到城市 3 3 3。到达城市 3 3 3 后,前面尚未旅行的城市为 4 4 4,所以城市 4 4 4 离城市 3 3 3 最近,但是如果要到达城市 4 4 4,则总路程为 2 + 3 = 5 > 3 2+3=5>3 2+3=5>3,所以小 B \text B B 会直接在城市 3 3 3 结束旅行。

如果从城市 3 3 3 出发,可以到达的城市为 4 4 4,由于没有离城市 3 3 3 第二近的城市,因此旅行还未开始就结束了。

如果从城市 4 4 4 出发,没有可以到达的城市,因此旅行还未开始就结束了。

【样例2说明】

x = 7 x=7 x=7 时,如果从城市 1 1 1 出发,则路线为 1 → 2 → 3 → 8 → 9 1 \to 2 \to 3 \to 8 \to 9 12389,小 A \text A A 走的距离为 1 + 2 = 3 1+2=3 1+2=3,小 B \text B B 走的距离为 1 + 1 = 2 1+1=2 1+1=2。(在城市 1 1 1 时,距离小 A \text A A 最近的城市是 2 2 2 6 6 6,但是城市 2 2 2 的海拔更高,视为与城市 1 1 1 第二近的城市,所以小 A \text A A 最终选择城市 2 2 2;走到 9 9 9 后,小 A \text A A 只有城市 10 10 10 可以走,没有第二选择可以选,所以没法做出选择,结束旅行)

如果从城市 2 2 2 出发,则路线为 2 → 6 → 7 2 \to 6 \to 7 267,小 A \text A A 和小 B \text B B 走的距离分别为 2 , 4 2,4 2,4

如果从城市 3 3 3 出发,则路线为 3 → 8 → 9 3 \to 8 \to 9 389,小 A \text A A 和小 B \text B B 走的距离分别为 2 , 1 2,1 2,1

如果从城市 4 4 4 出发,则路线为 4 → 6 → 7 4 \to 6 \to 7 467,小 A \text A A 和小 B \text B B 走的距离分别为 2 , 4 2,4 2,4

如果从城市 5 5 5 出发,则路线为 5 → 7 → 8 5 \to 7 \to 8 578,小 A \text A A 和小 B \text B B 走的距离分别为 5 , 1 5,1 5,1

如果从城市 6 6 6 出发,则路线为 6 → 8 → 9 6 \to 8 \to 9 689,小 A \text A A 和小 B \text B B 走的距离分别为 5 , 1 5,1 5,1

如果从城市 7 7 7 出发,则路线为 7 → 9 → 10 7 \to 9 \to 10 7910,小 A \text A A 和小 B \text B B 走的距离分别为 2 , 1 2,1 2,1

如果从城市 8 8 8 出发,则路线为 8 → 10 8 \to 10 810,小 A \text A A 和小 B \text B B 走的距离分别为 2 , 0 2,0 2,0

如果从城市 9 9 9 出发,则路线为 9 9 9,小 A \text A A 和小 B \text B B 走的距离分别为 0 , 0 0,0 0,0(旅行一开始就结束了)。

如果从城市 10 10 10 出发,则路线为 10 10 10,小 A \text A A 和小 B \text B B 走的距离分别为 0 , 0 0,0 0,0

从城市 2 2 2 或者城市 4 4 4 出发小 A \text A A 行驶的路程总数与小 B \text B B 行驶的路程总数的比值都最小,但是城市 2 2 2 的海拔更高,所以输出第一行为 2 2 2

【数据范围与约定】

对于 30 % 30\% 30% 的数据,有 1 ≤ n ≤ 20 , 1 ≤ m ≤ 20 1\le n \le 20,1\le m\le 20 1n20,1m20
对于 40 % 40\% 40% 的数据,有 1 ≤ n ≤ 100 , 1 ≤ m ≤ 100 1\le n \le 100,1\le m\le 100 1n100,1m100
对于 50 % 50\% 50% 的数据,有 1 ≤ n ≤ 100 , 1 ≤ m ≤ 1000 1\le n \le 100,1\le m\le 1000 1n100,1m1000
对于 70 % 70\% 70% 的数据,有 1 ≤ n ≤ 1000 , 1 ≤ m ≤ 1 0 4 1\le n \le 1000,1\le m\le 10^4 1n1000,1m104
对于 100 % 100\% 100% 的数据: 1 ≤ n , m ≤ 1 0 5 1\le n,m \le 10^5 1n,m105 − 1 0 9 ≤ h i ≤ 1 0 9 -10^9 \le h_i≤10^9 109hi109 1 ≤ s i ≤ n 1 \le s_i \le n 1sin 0 ≤ x i ≤ 1 0 9 0 \le x_i \le 10^9 0xi109
数据保证 h i h_i hi 互不相同。

完整代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<set>
using namespace std;
const int N=1e5+200,INF=2e9;
struct City
{int id,al;//identifier,altitudefriend bool operator < (City a,City b){return a.al<b.al; }
};
int n,m,x0,la,lb,ansid;
int h[N],s[N],x[N];
int f[20][N][5],da[20][N][5],db[20][N][5];
double ans=INF*1.0;
multiset<City> q;
void calc(int S,int X)
{int p=S;la=0,lb=0;for(int i=18;i>=0;i--)if(f[i][p][0] && la+lb+da[i][p][0]+db[i][p][0]<=X){la+=da[i][p][0];lb+=db[i][p][0];p=f[i][p][0];}
}
void pre()
{h[0]=INF,h[n+1]=-INF;City st;//startst.id=0,st.al=INF;q.insert(st),q.insert(st);st.id=n+1,st.al=-INF;q.insert(st),q.insert(st);for(int i=n;i;i--){int ga,gb;City now;now.id=i,now.al=h[i];q.insert(now);set<City>::iterator p=q.lower_bound(now);p--;int lt=(*p).id,lh=(*p).al;//lastp++,p++;int ne=(*p).id,nh=(*p).al;//nextp--;if(abs(nh-h[i])>=abs(h[i]-lh)){gb=lt;p--,p--;if(abs(nh-h[i])>=abs(h[i]-(*p).al))ga=(*p).id;elsega=ne;}else{gb=ne;p++,p++;if(abs((*p).al-h[i])>=abs(h[i]-lh))ga=lt;elsega=(*p).id;}//2、预处理f[0][i][0]=ga,f[0][i][1]=gb;da[0][i][0]=abs(h[i]-h[ga]);db[0][i][1]=abs(h[i]-h[gb]);//3、DP初值}for(int i=1;i<=18;i++)for(int j=1;j<=n;j++)for(int k=0;k<2;k++)if(i==1){f[1][j][k]=f[0][f[0][j][k]][1-k];da[1][j][k]=da[0][j][k]+da[0][f[0][j][k]][1-k];db[1][j][k]=db[0][j][k]+db[0][f[0][j][k]][1-k];	}else{f[i][j][k]=f[i-1][f[i-1][j][k]][k];da[i][j][k]=da[i-1][j][k]+da[i-1][f[i-1][j][k]][k];db[i][j][k]=db[i-1][j][k]+db[i-1][f[i-1][j][k]][k];}//3、倍增优化DP
}
int main()
{cin>>n;for(int i=1;i<=n;i++)scanf("%d",&h[i]);cin>>x0>>m;for(int i=1;i<=m;i++)scanf("%d%d",&s[i],&x[i]);//1、输入pre();for(int i=1;i<=n;i++){calc(i,x0);double nowans=(double)la/(double)lb;if(nowans<ans){ans=nowans;ansid=i;}elseif(nowans==ans && h[ansid]<h[i])ansid=i;}cout<<ansid<<endl;//4、求解问题1for(int i=1;i<=m;i++){calc(s[i],x[i]);printf("%d %d\n",la,lb);}//5、求解问题2return 0;
}

相关文章:

[NOIP2012 提高组] 开车旅行

[NOIP2012 提高组] 开车旅行 题目描述 小 A \text{A} A 和小 B \text{B} B 决定利用假期外出旅行&#xff0c;他们将想去的城市从 $1 $ 到 n n n 编号&#xff0c;且编号较小的城市在编号较大的城市的西边&#xff0c;已知各个城市的海拔高度互不相同&#xff0c;记城市 …...

数据库设计流程---以案例熟悉

案例名字&#xff1a;宠物商店系统 课程来源&#xff1a;点击跳转 信息->概念模型->数据模型->数据库结构模型 将现实世界中的信息转换为信息世界的概念模型&#xff08;E-R模型&#xff09; 业务逻辑 构建 E-R 图 确定三个实体&#xff1a;用户、商品、订单...

Miniconda创建paddlepaddle环境

1、conda env list 2、conda create --name paddle_env python3.8 --channel https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/free/ 3、activate paddle_env 4、python -m pip install paddlepaddle -i https://mirror.baidu.com/pypi/simple 5、pip install "p…...

postgresql实现单主单从

实现步骤 1.主库创建一个有复制权限的用户 CREATE ROLE 用户名login # 有登录权限的角色即是用户replication #复制权限 encrypted password 密码;2.主库配置开放从库外部访问权限 修改 pg_hba.conf 文件 &#xff08;相当于开放防火墙&#xff09; # 类型 数据库 …...

提取PDF数据:Documents for PDF ( GcPdf )

在当今数据驱动的世界中&#xff0c;从 PDF 文档中无缝提取结构化表格数据已成为开发人员的一项关键任务。借助GrapeCity Documents for PDF ( GcPdf )&#xff0c;您可以使用 C# 以编程方式轻松解锁这些 PDF 中隐藏的信息宝藏。 考虑一下 PDF&#xff08;最常用的文档格式之一…...

adb连接切换到模拟器端口

查看连接状态 adb devices出现以下情况 C:\Users\22560>adb devices List of devices attached 127.0.0.1:5555 offline emulator-5554 device可以发现我们想要连接的雷电模拟器的5555端口目前没有连接&#xff0c;只有emulator-5554被连接了&#xff0c;此时我们需要关…...

为何每个开发者都在谈论Go?

目录 一、引言Go的历史回顾关键时间节点 使用场景Go的语言地位技术社群与企业支持资源投入和生态系统 二、简洁的语法结构基本组成元素变量声明与初始化代码示例 类型推断函数与返回值代码示例输出 接口与结构体&#xff1a;组合而非继承错误处理&#xff1a;明确而不是异常小结…...

【Leetcode】 501. 二叉搜索树中的众数

给你一个含重复值的二叉搜索树&#xff08;BST&#xff09;的根节点 root &#xff0c;找出并返回 BST 中的所有 众数&#xff08;即&#xff0c;出现频率最高的元素&#xff09;。 如果树中有不止一个众数&#xff0c;可以按 任意顺序 返回。 假定 BST 满足如下定义&#xf…...

怎样给Ubuntu系统安装vmware-tools

首先我要告诉你&#xff1a;Ubuntu无法安装vmware-tools&#xff0c;之所以这么些是因为我一开始也是这样认为的&#xff0c;vmware-tools是给Windows系统准备的我认为&#xff0c;毕竟Windows占有率远远高于Linux&#xff0c;这也可以理解。 那么怎么样实现Ubuntu虚拟机跟Wind…...

DDS信号发生器波形发生器VHDL

名称&#xff1a;DDS信号发生器波形发生器 软件&#xff1a;Quartus 语言&#xff1a;VHDL 要求&#xff1a; 在EDA平台中使用VHDL语言为工具&#xff0c;设计一个常见信号发生电路&#xff0c;要求&#xff1a; 1. 能够产生锯齿波&#xff0c;方波&#xff0c;三角波&…...

Python3操作SQLite3创建表主键自增长|CRUD基本操作

Win11查看安装的Python路径及安装的库 Python PEP8 代码规范常见问题及解决方案 Python3操作MySQL8.XX创建表|CRUD基本操作 Python3操作SQLite3创建表主键自增长|CRUD基本操作 anaconda3最新版安装|使用详情|Error: Please select a valid Python interpreter Python函数绘…...

B. Comparison String

题目&#xff1a; 样例&#xff1a; 输入 4 4 <<>> 4 >><< 5 >>>>> 7 <><><><输出 3 3 6 2 思路&#xff1a; 由题意&#xff0c;条件是 又因为要使用尽可能少的数字&#xff0c;这是一道贪心题&#xff0c;所以…...

python端口扫描

扫描所有端口 import socket, threading, os, timedef port_thread(ip, start, step, timeout):for port in range(start, start step):s socket.socket()s.settimeout(timeout)try:s.connect((ip, port))print(f"port[{port}] 可用")except Exception as e:# pri…...

国庆第二天

#include<th.h>#define ERR_MSG(msg) do{\fprintf(stderr,"__%d__",__LINE__);\perror(msg);\ }while(0)#define PORT 6666 #define IP "192.168.2.3"//键盘输入事件 int serverkeyboard(fd_set readfds) {char buf[128] "";int sndfd -…...

Java安全之servlet内存马分析

目录 前言 什么是中间键 了解jsp的本质 理解servlet运行机制 servlet的生命周期 Tomcat总体架构 查看Context 的源码 servlet内存马实现 参考 前言 php和jsp一句话马我想大家都知道&#xff0c;早先就听小伙伴说过一句话木马已经过时了&#xff0c;现在是内存马的天下…...

2023年第二十届中国研究生数学建模竞赛总结与分享

今天是国庆节&#xff0c;祝祖国繁荣富强。正好也学习不下去&#xff0c;就想着写写博客&#xff0c;总结一下自己在参加2023年第20届中国研究生数学建模比赛的一些感受。 目录 1.基本介绍 2.比赛分享 1.基本介绍 1. 竞赛时间&#xff1a;竞赛定于2023年9月22日8:00至2023年9…...

Web前端-Vue2+Vue3基础入门到实战项目-Day1(初始Vue, Vue指令, 小黑记事本)

Web前端-Vue2Vue3基础入门到实战项目-Day1 Vue快速上手创建一个Vue实例插值表达式Vue响应式特性 Vue指令指令初识 和 v-htmlv-show 和 v-ifv-else 和 v-else-ifv-on内联语句methods处理函数调用传参 v-bind案例 - 波仔的学习之旅v-forv-for基本使用案例 - 小黑的书架v-for的key…...

Sentinel学习(2)——sentinel的使用,引入依赖和配置 对消费者进行流控 对生产者进行熔断降级

前言 Sentinel 是面向分布式、多语言异构化服务架构的流量治理组件&#xff0c;主要以流量为切入点&#xff0c;从流量路由、流量控制、流量整形、熔断降级、系统自适应过载保护、热点流量防护等多个维度来帮助开发者保障微服务的稳定性。 本篇博客介绍sentinel的使用&#x…...

springboot 简单配置mongodb多数据源

准备工作&#xff1a; 本地mongodb一个创建两个数据库 student 和 student-two 所需jar包&#xff1a; # springboot基于的版本 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId>&l…...

西门子S7-1200使用LRCF通信库与安川机器人进行EthernetIP通信的具体方法示例

西门子S7-1200使用LRCF通信库与安川机器人进行EthernetIP通信的具体方法示例 准备条件: PLC:S7-1200 1214C DC/DC/DC 系统版本4.5及以上。 机器人控制柜:安川YRC1000。 软件:TIA V17 PLC做主站,机器人做从站。 具体方法可参考以下内容: 使用的库文件为西门子 1200系列…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...

【WebSocket】SpringBoot项目中使用WebSocket

1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖&#xff0c;添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...

规则与人性的天平——由高考迟到事件引发的思考

当那位身着校服的考生在考场关闭1分钟后狂奔而至&#xff0c;他涨红的脸上写满绝望。铁门内秒针划过的弧度&#xff0c;成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定"&#xff0c;构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...