文档章节

PAT——A1046

Cinzano
 Cinzano
发布于 2017/05/21 23:08
字数 522
阅读 6
收藏 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
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
2.9K
0
PAT 1003. 我要通过!(20)

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

xnh_565175944
2017/12/03
0
0
Speak my true name, summon my constructor

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

Felis sapiens
2017/04/20
0
0
asa 动态地址的转化,以及,端口映射

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

kf690621683
01/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

人生苦短:Python里的17个“超赞操作

人生苦短,我选Python”。那么,你真的掌握了Python吗? 1. 交换变量 有时候,当我们要交换两个变量的值时,一种常规的方法是创建一个临时变量,然后用它来进行交换。比如: # 输入 a = 5 b ...

糖宝lsh
47分钟前
4
0
咕泡-spring中常用设计模式概述

设计模式就是经验之谈,供后人借鉴,解决一些具有代表性的问题 设计模式来源于生活,反过来帮助我们更好生活 设计模式提升代码的可读性、可扩展性、维护成本、复杂业务问题 千万不要死记硬背...

职业搬砖20年
今天
2
0
day59-20180817-流利阅读笔记-待学习

假·照骗,真·社交焦虑 雪梨 2018-08-17 1.今日导读 发朋友圈之前,不少人为了展现更美好的生活状态会对照片加以“微调”,或是加个滤镜显得逼格更高,或是磨个皮瘦个脸拉个大长腿。现在,国...

aibinxiao
今天
23
0
OSChina 周五乱弹 —— 姑娘在这个节日里表白你接受么?

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @Sharon啊:完全被这个小姐姐圈粉了,学两首她的歌去哈哈 分享王贰浪的单曲《往后余生(翻自 马良)》 《往后余生(翻自 马良)》- 王贰浪 手...

小小编辑
今天
1K
17
为什么HashMap要自己实现writeObject和readObject方法?

为什么HashMap要自己实现writeObject和readObject方法? 如果你有仔细阅读过HashMap的源码,那么你一定注意过一个问题:HashMap中有两个私有方法。 private void writeObject(java.io.Objec...

DemonsI
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部