1046 Shortest Distance

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,10^5]), 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 (≤10^4), 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 10^7.

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

题目大意

一个甜甜圈，求该圈上标准的任意两点间，抵达的最短距离

思路

记甜甜圈的总长为sum，length[z]表示点z抵达点1的距离，lebgth[1] = 0

那么任意两点A与B间的最短距离为

min(sum-abs(length[A]-length[B]),abs(length[A]-length[B]))

C/C++


#include
using namespace std;
int main()
{
    int N,length[100001]={0},sumLen=0,len;
    cin >> N;
    for(int z=1;z<=N;z++){
        cin >> len;
        length[z+1] = sumLen = sumLen + len;
    }
    cin >> N;
    while (N--){
        int a,b;
        cin >> a >> b;
        int minRoad = abs(length[a]-length[b]);
        minRoad = min(minRoad,sumLen-minRoad);
        cout << minRoad << endl;
    }
    return 0;
}

相关阅读:
MySQL Binlog 简介
opencv-python图像处理：阈值，滤波，腐蚀，膨胀，梯度
提高采购效率，采购管理的五大原则及实现方法
【PAT (Advanced Level) Practice】1011 World Cup Betting (20 分)python题解
2021数据库年度回顾，PostgreSQL占主导，Cloudera面临破产
720云手机电动云台全新上市，让手机能自动拍摄亿万像素VR全景
（四） ES6 新特性 —— 参数默认值与spread扩展运算符
Windows上使用client-go远程访问安装在本地WMware上的Linux虚拟机里的minikube
nacos注册发现原理
【无标题】

原文地址：https://blog.csdn.net/daybreak_alonely/article/details/127824714