1046 Shortest Distance (20 分)
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<stdio.h>
#include<stdlib.h>
#define MaxN 100001
int GettingData(int *D);
int main()
{
int sum,dis,antidis;
int m,i;
int s,d,tmp;
int distance[MaxN];
sum=GettingData(distance);
scanf("%d",&m);
for(i=0;i<m;i++){
scanf(" %d %d",&s,&d);
if(s>d){tmp=s;s=d;d=tmp;}
dis=distance[d]-distance[s];
antidis=sum-dis;
if(dis<antidis) printf("%d\n",dis);
else printf("%d\n",antidis);
}
return 0;
}
int GettingData(int *D)
{
int i,t,sum=0;
scanf("%d",&D[0]);
for(i=1;i<=D[0];i++){
scanf("%d",&t);
D[i]=sum;
sum+=t;
}
return sum;
}
二、不太聪明的解答：
每组测试数据都要遍历一遍数组，时间复杂度接近O(N)，超时了，若对数据进行处理，时间复杂度可降低为O(1)。
#include<stdio.h>
#include<stdlib.h>
#define MaxN 100001
#define MaxM 20001
void GettingData(int *D,int *T);
void ShortestDistance(int *D,int *T);
int main()
{
int distance[MaxN],test[MaxM];
GettingData(distance,test);
ShortestDistance(distance,test);
return 0;
}
void ShortestDistance(int *D,int *T)
{
int i=1,j,tmp;
int s,d;
int dis,antidis;
while(i<2*T[0]){
dis=0,antidis=0;
s=T[i++];d=T[i++];
if(s>d){tmp=s;s=d;d=tmp;}
if(s<0||d>D[0]) break;
for(j=s;j!=d;j=j%D[0]+1)
dis+=D[j];
for(j=d;j!=s;j=j%D[0]+1)
antidis+=D[j];
if(dis<antidis) printf("%d\n",dis);
else printf("%d\n",antidis);
}
}
void GettingData(int *D,int *T)
{
int i;
scanf("%d",&D[0]);
for(i=1;i<=D[0];i++)
scanf("%d",&D[i]);
scanf("%d",&T[0]);
for(i=1;i<=2*T[0];i++)
scanf(" %d",&T[i]);
return;
}