文档章节

PAT A1046. Shortest Distance (20)

 阿豪boy
发布于 2017/02/25 10:53
字数 337
阅读 5
收藏 0
点赞 0
评论 0

https://www.patest.cn/contests/pat-a-practise/1046

时间限制

100 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

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 <iostream>
#include <cstdio> 

//dis[i] 表示 由 1出发到i的距离 
//由a到b的距离就是 dis[b]-dis[a] 默认a<b 
  
int dis[100010];
using namespace std;
int main(int argc, char *argv[])
{
	int n,t,m;
	scanf("%d",&n);
	dis[1]=0; 
	int sum=0;  //环的总长 
	for(int i=2;i<=n+1;i++){
		scanf("%d",&t);
		dis[i]=dis[i-1]+t;	
		sum += t;
	}
	scanf("%d",&m);
	while(m--){
		int a,b;
		scanf("%d%d",&a,&b);
		if(a>b) swap(a,b);
		printf("%d\n",min( dis[b]-dis[a],sum-(dis[b]-dis[a])) ); 	
	} 
	return 0;
}

 

© 著作权归作者所有

共有 人打赏支持
粉丝 21
博文 971
码字总数 665601
作品 0
西安
Pathfinding Algorithms in C#

Download source - 571.3 KB Path finding challenge Unzip and open solution in Visual Studio 2017 Introduction Have you ever wondered how GPS applications calculate the fastest wa......

KristianEkman
2017/12/22
0
0
821. Shortest Distance to a Character - LeetCode

Question 821. Shortest Distance to a Character Solution 思路:遍历字符串S,遇到与字符C相等就分别向左/右计算其他字符与该字符的距离,如果其他字符就是C或与目标字符的距离更小的话遍历...

yysue
06/28
0
0
CSU 2088: Pigs can't take a sudden turn(简单的计算几何)

题目链接 Pigs can’t take a sudden turn Time limit:1000 ms Memory limit:65536 kB Problem Descrpition You maybe have ACed a question about computational geometry,which describes......

xp731574722
04/22
0
0
[Python] (Day-18) - List 列表实际操作

The shortest distance between two people is a smile. 人与人之间最短的距离是微笑。 List 列表实际操作练习 1、List 定义 2、List 负数索引 3、List 增加元素 4、List 搜索 5、List 删除元...

Mazy
2017/10/27
0
0
[Week 1] Princeton Algorithm PartII WordNet

最近在coursera上学习Princeton大学的Algorithm PartII,这个系列的两门课是我见过最好的算法课。主讲Robert Sedgewick师承高德纳,声名远播,虽然年纪大了,但是讲课思路清晰,深入浅出。与...

lyy0905
2017/01/25
0
0
给出两个单词,找到它们的最短距离 (以它们之间隔了多少个单词计数)。

有一篇文章内含多个单词,现给定两个单词,请设计一个高效算法,找出文中这两个单词的最短距离(即最少相隔的单词数,也就是两个单词在文章中位置的差的绝对值)。 给定一个string数组article,...

一贱书生
2016/11/28
10
0
路由协议中部分英文简称的全称

ACL : Access Control List - 访问 控制 列表NAT: Network Address Translation : 网络地址转换DHCP : dynamic host configuration protocol - 动态主机配置协议IGP:Internet Gateway Prot......

甄江
01/04
0
0
路由协议概述(1) --- 总览

心理表征 自治系统,路由算法,主要协议 自治系统(AS:autonomous system) 自治系统其实就像国家划分了不同的省份,各省有自己的的管理条例,路由也是类似。 两个原因。1.数量庞大。若没有...

zcx1128
2017/07/04
0
0
交换机 DHCP 协议与配置

DHCP dynamic host configuration protocol 动态的 主机配置协议 静态的 -配置内容 IP -作用 自动的为终端设备,分配IP地址; -角色 DHCP 服务器 DHCP 客户端 -配置: 1、配置DHCP客户端 -将...

云之眼
2017/11/13
0
0
再译《A *路径搜索入门》之二

■路径评分 Path Scoring 计算出的路径时,确定要使用的方格的关键是下面的公式: The key to determining which squares to use when figuring out the path is the following equation: F ...

放个屁
2015/06/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Docker Mac (三) Dockerfile 及命令

Dockerfile 最近学习docker的时候,遇到一件怪事,关于docker镜像可能会被破坏,还不知道它会有此措施 所以需要了解构建Dockerfile的正确方法 Dockerfile是由一系列命令和参数构成的脚本,这些命...

___大侠
22分钟前
0
0
NetCat Tutorials

Hacking with Netcat part 1: The Basics Hacking with Netcat part 2: Bind and reverse shells Hacking with Netcat part 3: Advanced Techniques 10 Introduction to Netcat - pdf NetCat......

zungyiu
22分钟前
0
0
Android Studio+NDK+Cmake 移植FFmpeg-4.0.2命令行工具

一、编译 参考大神的帖子,亲测一次编译成功:https://blog.csdn.net/bobcat_kay/article/details/80889398 鉴于以前查文档的经验,这里附上编写例子的时间:2018年7月22日 我用的是ubantu,...

她叫我小渝
23分钟前
0
0
mysql创建数据库

登录MYSQL mysql -u root -p 脚本创建数据库WeChat,并制定默认的字符集是utf8mb4。 CREATE DATABASE Wechat DEFAULT CHARSET utf8mb4 COLLATE utf8mb4_general_ci; 授权 grant all......

niithub
37分钟前
0
0
svn: Unable to connect to a repository URL 的解决方案

错误图示: 解决办法:清除本地保存的授权信息; 1:右键点击本地文件夹,选择设置; TortoiseSVN -> Settings 2:在弹出的对话框中选择 Saved Data, 右侧选择:授权地方清理所有。 然后点确...

宁哥实战课堂
今天
1
0
sleep与wait的区别

Thread.sleep(XXX)方法消耗CPU吗? 这个知识点是我之前认识一直有错误的一个知识点,在我以前的认识里面,我一直认为Thread.sleep(1000)的这一秒钟的时间内,线程的休眠是一直占用着CPU的时间...

码代码的小司机
今天
1
0
20位活跃在Github上的国内技术大牛 leij 何小鹏 亚信

本文列举了20位在Github上非常活跃的国内大牛,看看其中是不是很多熟悉的面孔? 1. lifesinger(玉伯) Github主页: https://github.com/lifesinger 微博:@ 玉伯也叫射雕 玉伯(王保平),...

海博1600
今天
1
0
Mybatis收集配置

一、Mybatis取Clob数据 1、Mapper.xml配置 <resultMap type="com.test.User" id="user"> <result column="id" property="id"/> <result column="json_data" property="jsonData" ......

星痕2018
今天
1
0
centos7设置以多用户模式启动

1、旧版本linux系统修改inittab文件,在新版本执行vi /etc/inittab 会有以下提示 # inittab is no longer used when using systemd. # # ADDING CONFIGURATION HERE WILL HAVE NO EFFECT ON......

haha360
今天
1
0
OSChina 周日乱弹 —— 局长:怕你不爱我

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ andonny :分享周二珂的单曲《孤独她呀》 《孤独她呀》- 周二珂 手机党少年们想听歌,请使劲儿戳(这里) @孤星闵月 :没事干,看一遍红楼梦...

小小编辑
今天
395
12

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部