(PAT 1046) Shortest Distance (递推)

忘是亡心i 2022-03-20 04:45 168阅读 0赞

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 <algorithm>
    using namespace std;
    int MaxArray[100010] = { 0 };
    
    int main() {
    	int Nn,temp;
    	int sum = 0;
    	scanf("%d", &Nn);
    	for (int i = 1; i <= Nn; ++i) {
    		scanf("%d", &temp);
    		sum += temp;
    		MaxArray[i] = sum;
    	}
    	//递推法
    	int Nm;
    	int nleft, nright;
    	scanf("%d", &Nm);
    	for (int i = 0; i < Nm; ++i) {
    		scanf("%d %d", &nleft, &nright);
    		if (nleft > nright) swap(nleft, nright);
    		int res = MaxArray[nright - 1] - MaxArray[nleft - 1];
    		printf("%d\n", min(res,sum-res));
    	}
    
    	system("PAUSE");
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，168人围观）

还没有评论，来说两句吧...

相关阅读

相关 1046 Shortest Distance（前缀和）

1046 Shortest Distance（前缀和） 0、题目 The task is really simple: given N exits on a hig

缺乏、安全感/ 2024年04月07日 12:35/ 0 赞/ 63 阅读

相关 1046 Shortest Distance (20 分) PAT 我的代码+别人的代码

1046 Shortest Distance (20 分) The task is really simple: given N exits on a highway whi

迈不过友情╰/ 2024年02月19日 20:52/ 0 赞/ 64 阅读

相关 1046. Shortest Distance (20)

The task is really simple: given N exits on a highway which forms a simple cycle, you ar

迈不过友情╰/ 2022年05月31日 12:54/ 0 赞/ 145 阅读

相关 PAT乙级1046

1047 编程团体赛（20 分）编程团体赛的规则为：每个参赛队由若干队员组成；所有队员独立比赛；参赛队的成绩为所有队员的成绩和；成绩最高的队获胜。现给定所有队员的比赛

Myth丶恋晨/ 2022年05月11日 15:14/ 0 赞/ 179 阅读

相关 PAT乙级1046

1046 划拳（15 分）划拳是古老中国酒文化的一个有趣的组成部分。酒桌上两人划拳的方法为：每人口中喊出一个数字，同时用手比划出一个数字。如果谁比划出的数字正好等于两人喊

╰+攻爆jí腚メ/ 2022年05月06日 11:57/ 0 赞/ 210 阅读

相关 1046 Shortest Distance（最短距离）

problem description The task is really simple: given N exits on a highway which for

男娘i/ 2022年04月16日 04:53/ 0 赞/ 214 阅读

相关 (PAT 1046) Shortest Distance (递推)

The task is really simple: given N exits on a highway which forms a simple cycle, you ar

忘是亡心i/ 2022年03月20日 04:45/ 0 赞/ 169 阅读

相关 (PAT 1101) Quick Sort (递推)

There is a classical process named partition in the famous quick sort algorithm. In this

￡神魔★判官ぃ/ 2022年03月16日 00:46/ 0 赞/ 193 阅读

相关 PAT A1046 Shortest Distance

The task is really simple: given N exits on a highway which forms a simple cycle, you ar

缺乏、安全感/ 2021年10月01日 05:54/ 0 赞/ 230 阅读

相关 PAT A1046 Shortest Distance (20)

题目地址：[https://www.patest.cn/contests/pat-a-practise/1046][https_www.patest.cn_contests_p

- 日理万妓/ 2021年09月13日 22:18/ 0 赞/ 247 阅读