文档章节

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
网络穿透与音视频技术(1)——NAT的概念及工作模式(上)

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

说好不能打脸
09/14
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
2.9K
0

没有更多内容

加载失败,请刷新页面

加载更多

解决访问swaggerUI接口文档显示basic-error-controler问题

使用swagger生成接口文档后,访问http://localhost:8888/swagger-ui.html#/,显示如下: 解决方法: public Docket createRestApi() {return new Docket(DocumentationType.SWAGGER_2)......

张欢19933
26分钟前
1
0
区块链教程以太坊源码分析core-state-process源码分析(二)

兄弟连区块链教程以太坊源码分析core-state-process源码分析(二):关于g0的计算,在黄皮书上由详细的介绍和黄皮书有一定出入的部分在于if contractCreation && homestead {igas.SetUin...

兄弟连区块链入门教程
31分钟前
0
0
BLAKE2 — fast secure hashing

BLAKE2 — fast secure hashing SPECS | CODE | B2SUM | CONTACT | USERS | THIRD-PARTY SOFTWARE | CRYPTANALYSIS | FAQ Come from http://www.blake2.net/ BLAKE2 is a cryptographic has......

openthings
37分钟前
4
0
Titan Framework MongoDB深入理解3

在前两篇文章中,我们介绍了操作Mongo数据库的类型Curd和Finder,下面要理解的是框架内mongoDB操作的条件类型——MongoDBQueryCondition。 MongoDBQueryCondition是一个接口,规定了一些实现...

云季科技
37分钟前
0
0
数据结构(算法)-树

#include <iostream>#include <malloc.h>using namespace std;#define MaxSize 100typedef char ElemType;typedef struct node{ElemType data;struct node *left ,*......

ashuo
39分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部