1,题目描述
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 的距离。
给出任意两个出口,输出两个出口间的最短距离。
输入
- 第一行:出口数目N,N个相邻出口间的距离;
- 第二行:需要计算的出口对数M;
- 其余M行:M对出口;
输出
- 每对出口输出一次,占一行;
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