阿豪boy

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;
}``````

阿豪boy

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(简单的计算几何)

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

lyy0905
2017/01/25
0
0

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

zcx1128
2017/07/04
0
0

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

2017/11/13
0
0

■路径评分 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命令行工具

23分钟前
0
0
mysql创建数据库

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

1
0
sleep与wait的区别

1
0
20位活跃在Github上的国内技术大牛 leij 何小鹏 亚信

1
0
Mybatis收集配置

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