文档章节

PAT——A1046

Cinzano
 Cinzano
发布于 2017/05/21 23:08
字数 522
阅读 8
收藏 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
合肥
其他
私信 提问
PAT A1046. Shortest Distance (20)

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 exi......

阿豪boy
2017/02/25
0
0
PAT B1003. 我要通过!(20)

我要通过!(20) https://www.patest.cn/contests/pat-b-practise/1003 时间限制 400 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 CHEN, Yue “答案正确”是自动判题系...

阿豪boy
2017/03/01
0
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
3K
0
网络穿透与音视频技术(1)——NAT的概念及工作模式(上)

版权声明:欢迎转载,但是看在我辛勤劳动的份上,请注明来源:http://blog.csdn.net/yinwenjie(未经允许严禁用于商业用途!) https://blog.csdn.net/yinwenjie/article/details/82622234 (...

说好不能打脸
09/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CPU性能过剩提升乏力影响未来行业发展吗?

虽然CPU仍然在不断发展,但是它的性能已经不再仅仅受限于单个处理器类型或制造工艺上了。和过去相比,CPU性能提升的步伐明显放缓了,接下来怎么办,成为横亘在整个行业面前的大问题。 自201...

linuxCool
8分钟前
0
0
使用Autowired和Qualifier解决多个相同类型的bean如何共存的问题

注意: 实现类UserServiceImpl,MyUserServiceImpl 需要区分:@Service("userServicel") @Service("myUserService") https://blog.csdn.net/russle/article/details/80287763......

qimh
42分钟前
3
0
SQL 语句使用to_char函数时,检索结果有空格

小疯在使用Oracle过程中,使用to_char函数检索表数据时发现检索结果前面会有一个空格,对后续开发有影响。问题很好解决,比较直接对可以做一下trim处理。但是小疯很疑惑为什么会有空格呢,于...

野小疯
44分钟前
3
0
对接比特币钱包的PHP开发包

BtcTool是一个基于第三方服务和离线裸交易实现的PHP比特币应用开发包,适合不希望部署本地 节点旳PHP开发者,开发包主要包含以下特性: 利用第三方服务获取指定地址的utxo集合 离线生成消费裸...

汇智网教程
今天
2
0
【自用】 VHD to VHDX

VHDX: 在VHD 2TB 的基础上提供 64TB的容量。 支持逻辑扇区大小为 4KB,和每块的大小为 256MB,来优化虚拟磁盘性能。 比VHD提供更高的安全性、可靠性和性能。 convert-VHD –path d:\Hyper-v...

Tensor丨思悟
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部