文档章节

PAT——A1046

Cinzano
 Cinzano
发布于 2017/05/21 23:08
字数 522
阅读 6
收藏 0
点赞 0
评论 0
PAT

The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.

Input Specification:

Each input file contains one test case. For each case, the first line contains an integer N (in [3, 105]), followed by N integer distances D1 D2 ... DN, where Di is the distance between the i-th and the (i+1)-st exits, and DN is between the N-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M (<=104), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than 107.

Output Specification:

For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.

Sample Input:

5 1 2 4 14 9
3
1 3
2 5
4 1

Sample Output:

3
10
7

提交代码

#include<stdio.h>
int main(){
	int N,a[100000]={0},t,count=0;
	scanf("%d",&N);//N表示即将要输入的exits数; 
	for(int i=2;i<=N;i++){
		scanf("%d",&t);//t表示即将输入的每两个exits之间的distance; 
		a[i]=a[i-1]+t;//a[i]表示1-st exit to i-th 的 total distance; 
	}
	scanf("%d",&t);//this input is the last in N, this 't' is the distance of N-th to 1-st;
	count=a[N]+t;//count equal 前N个出口总距离 + 最后一个输入的第N个exit到第一个exit的距离; 
	int M,x,y,m=0;
	scanf("%d",&M);
	while(M--){
		scanf("%d %d",&x,&y);
		if(x>y){
			int temp=x;
			x=y;
			y=temp;
		}
		m=a[y]-a[x];//m is the distance of x-th to y-th; 
		int min=m<(count-m)? m:(count-m);//short distance need comparing;
		printf("%d\n",min);
		m=0;
	}
}

注意点:一开始我是数组表示每两个exits之间距离,底下求x-y距离时就要用到循环,而此循环是嵌套在while(M--)里的,时间复杂度就变成N^2了,在PAT第三个多点测试就会出现运行超时,所以稍作修改:用数组表示第1个exit到第i个exit之间总距离,这样下面求x-y距离时就可以不用循环。这里的整个环cycle总距离等于第1个exit到第N个exit的总距离 + 最后输入的N到第一个之间的距离。

 

© 著作权归作者所有

共有 人打赏支持
Cinzano
粉丝 0
博文 19
码字总数 6205
作品 0
合肥
其他
华为 vpn 配置 实现

实验名成:华为vpn配置实现 实验拓扑图: 3. 实验目的 :1. 使内网 172.16.10.0 配置vpn虚拟专用网可以访问AR3内网 web 服务器 2. 使内网 172.16.20.0 网段,配置动态pat可以上外网 4. 地址规...

kf690621683 ⋅ 02/08 ⋅ 0

静态、动态NAT、PAT的配置

本实验基于上一个ACL的实验 在VLAN7上添加两台PC.IP为:172.17.117.2、172.17.117.3。ACL等配置不变。 网络设备只允许技术登陆 SERVER 1:WWW 允许HTTP,PING 禁其它服务。 192.168.1.1/24 SER...

长平狐 ⋅ 2013/09/17 ⋅ 0

PAT 1003. 我要通过!(20)

“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于PAT的“答案正确”大派送 —— 只要读入的字符串满足下列条件,系统就输出“答案正确”,否则输出“答案错误”。 得到“答案正确...

xnh_565175944 ⋅ 2017/12/03 ⋅ 0

Speak my true name, summon my constructor

众所周知,Haskell 有选择性 export 的机制,可以用来隐藏一个数据类型的定义。大多数时候这个特性是好的,它是 modularity 的关键——库作者只提供一个数据类型的名字和 kind signatures,以...

Felis sapiens ⋅ 2017/04/20 ⋅ 0

vrrp ,网关冗余,浮动路由,pat地址转化,web服务器映射

实验名称:vrry ,网关冗余,浮动路由,pat地址转化,web服务器映射 实验拓扑图: 3.实验目的:1 .使内网可以访问web服务器 -server4 2. 配置vrrp使网关冗余备份,并且链路追踪 ,并且配置浮动...

kf690621683 ⋅ 02/02 ⋅ 0

asa 动态地址的转化,以及,端口映射

asa 动态地址的转化,以及端口的映射 实验拓扑图 4. 实验目的 : 1. 将内网 10.1.1.0 ,10.2.2.0 网段 通过pat转换 能够访问外网 ftp服务器 2. 将内网dmaz区的web,ftp分别做映射,使从外网可...

kf690621683 ⋅ 01/31 ⋅ 0

只需几步即可提升你的 SQL 技能

如果你习惯了使用 ActiveRecord 或者 SQLAlchemy,当你需要编写 SQL 的时候就会茫然失措,但,并不是只有你一个人会这样。 只需要一些时间来练习,你就可以像专家一样编写高级的查询。 坚实的...

OSC编辑部 ⋅ 2015/08/05 ⋅ 9

CCNA学习笔记之NAT

目标: 1、了解NAT的作用和工作原理 2、了解各种NAT术语 3、掌握NAT的各种配置(静态NAT、动态NAT、PAT和端口映射) 一、NAT基础: 1、什么是NAT: Network Address Translation,即网络地址...

土豆呼叫地瓜 ⋅ 2014/04/09 ⋅ 0

TS文件格式详解

首先是各种流的概念 ES流(Elementary Stream): 也叫基本码流,包含视频、音频或数据的连续码流. PES流(Packet Elementary Stream): 也叫打包的基本码流, 是将基本的码流ES流根据需要分成长度不...

lyon007 ⋅ 2016/09/01 ⋅ 0

Linux自学笔记——sed命令

sed行编辑器: sed是一种行编辑器,它一次处理一行内容。处理时,把当前处理的行存储在临时存储区中,称为“模式空间”,接着用sed命令处理缓冲区中的内容,处理完成后,把缓冲区的内容送往屏...

claude_liu ⋅ 2017/09/14 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Centos7重置Mysql 8.0.1 root 密码

问题产生背景: 安装完 最新版的 mysql8.0.1后忘记了密码,向重置root密码;找了网上好多资料都不尽相同,根据自己的问题总结如下: 第一步:修改配置文件免密码登录mysql vim /etc/my.cnf 1...

豆花饭烧土豆 ⋅ 今天 ⋅ 0

熊掌号收录比例对于网站原创数据排名的影响[图]

从去年下半年开始,我在写博客了,因为我觉得业余写写博客也还是很不错的,但是从2017年下半年开始,百度已经推出了原创保护功能和熊掌号平台,为此,我也提交了不少以前的老数据,而这些历史...

原创小博客 ⋅ 今天 ⋅ 0

LVM讲解、磁盘故障小案例

LVM LVM就是动态卷管理,可以将多个硬盘和硬盘分区做成一个逻辑卷,并把这个逻辑卷作为一个整体来统一管理,动态对分区进行扩缩空间大小,安全快捷方便管理。 1.新建分区,更改类型为8e 即L...

蛋黄Yolks ⋅ 今天 ⋅ 0

Hadoop Yarn调度器的选择和使用

一、引言 Yarn在Hadoop的生态系统中担任了资源管理和任务调度的角色。在讨论其构造器之前先简单了解一下Yarn的架构。 上图是Yarn的基本架构,其中ResourceManager是整个架构的核心组件,它负...

p柯西 ⋅ 今天 ⋅ 0

uWSGI + Django @ Ubuntu

创建 Django App Project 创建后, 可以看到路径下有一个wsgi.py的问题 uWSGI运行 直接命令行运行 利用如下命令, 可直接访问 uwsgi --http :8080 --wsgi-file dj/wsgi.py 配置文件 & 运行 [u...

袁祾 ⋅ 今天 ⋅ 0

JVM堆的理解

在JVM中,我们经常提到的就是堆了,堆确实很重要,其实,除了堆之外,还有几个重要的模块,看下图: 大 多数情况下,我们并不需要关心JVM的底层,但是如果了解它的话,对于我们系统调优是非常...

不羁之后 ⋅ 昨天 ⋅ 0

推荐:并发情况下:Java HashMap 形成死循环的原因

在淘宝内网里看到同事发了贴说了一个CPU被100%的线上故障,并且这个事发生了很多次,原因是在Java语言在并发情况下使用HashMap造成Race Condition,从而导致死循环。这个事情我4、5年前也经历...

码代码的小司机 ⋅ 昨天 ⋅ 2

聊聊spring cloud gateway的RetryGatewayFilter

序 本文主要研究一下spring cloud gateway的RetryGatewayFilter GatewayAutoConfiguration spring-cloud-gateway-core-2.0.0.RC2-sources.jar!/org/springframework/cloud/gateway/config/G......

go4it ⋅ 昨天 ⋅ 0

创建新用户和授予MySQL中的权限教程

导读 MySQL是一个开源数据库管理软件,可帮助用户存储,组织和以后检索数据。 它有多种选项来授予特定用户在表和数据库中的细微的权限 - 本教程将简要介绍一些选项。 如何创建新用户 在MySQL...

问题终结者 ⋅ 昨天 ⋅ 0

android -------- 颜色的半透明效果配置

最近有朋友问我 Android 背景颜色的半透明效果配置,我网上看资料,总结了一下, 开发中也是常常遇到的,所以来写篇博客 常用的颜色值格式有: RGB ARGB RRGGBB AARRGGBB 这4种 透明度 透明度...

切切歆语 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部