首页 > 编程语言 >PAT_甲级_1046 Shortest Distance (20分) (C++)【签到题】

PAT_甲级_1046 Shortest Distance (20分) (C++)【签到题】

时间:2022-10-27 16:00:53浏览次数:45  
标签:Distance PAT 1046 temp int sum 出口 data ans2


 

1,题目描述

PAT_甲级_1046 Shortest Distance (20分) (C++)【签到题】_甲级

Sample Input:

5 1 2 4 14 9
3
1 3
2 5
4 1

 

Sample Output:

3
10
7

题目大意

有N个出口,从1开始,依次给出出口 i+1 ~ i 的距离(i从1开始)。最后一个数字为 1~N 的距离。

给出任意两个出口,输出两个出口间的最短距离。

输入

  1. 第一行:出口数目N,N个相邻出口间的距离;
  2. 第二行:需要计算的出口对数M;
  3. 其余M行:M对出口;

输出

  1. 每对出口输出一次,占一行;

 

2,思路

输入数据时,每个点存放的是从1到该点的距离sum += temp;data[i] = sum;

a到b的最短距离(假设a<b),要么为data[b] - data[a],要么为sum - (data[b] - data[a])(sum为所有距离之和)。取最小值即可;

 

3,代码

#include<iostream>
#include<vector>
#include<math.h>
#include<climits>
using namespace std;

int main(){
//#ifdef ONLINE_JUDGE
//#else
// freopen("1.txt", "r", stdin);
//#endif

int N, M;
cin>>N;

int data[100002] = {0}, sum = 0, temp;
for(int i = 2; i <= N + 1; i++){ //data[1]=0 data[i]表示从1到i的距离
scanf("%d", &temp);
sum += temp;
data[i] = sum;
}

int a, b, ans1, ans2;
cin>>M;
for(int i = 0; i < M; i++){
scanf("%d %d", &a, &b);
if(a > b) swap(a, b); //保证a<b
ans1 = data[b]-data[a];
ans2 = sum-(data[b]-data[a]);
printf("%d\n", min(ans1, ans2));
}

return 0;
}

 

 

标签:Distance,PAT,1046,temp,int,sum,出口,data,ans2
From: https://blog.51cto.com/u_15849465/5801394

相关文章