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

迈不过友情╰ 2024-02-19 20:52 65阅读 0赞

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

这道题，我刚开始用的是数组，直接模拟，注意边界即可 （下面的代码只得17分 ，第三个测试点数据太大，超时了）

#include<stdio.h>
    int a[100005];
    int main()
    {
    	int i,j,n,m,sum1=0,sum2=0,k1,k2;
    	scanf("%d",&n);
    	for(i=1;i<=n;i++)
    	scanf("%d",&a[i]);
    	scanf("%d",&m);
    	for(i=0;i<m;i++)
    	{
    		sum1=0;
    		sum2=0;
    		scanf("%d %d",&k1,&k2);
    		if(k1>k2)           //交换 看k1和k2，保证k1<k2 
    		{
    			int temp=k1;
    			k1=k2;
    			k2=temp;
    		}
    		for(j=k1;j<k2;j++)   //从k1右侧开始相加 
    		{
    			sum1+=a[j];
    		}
    	    for(j=k2;j<=n;j++)   // c从k1左侧开始计算 ，分为两部分 ，一部分是k2右侧，一部分是k1左侧 
    	    sum2+=a[j];
    	    for(j=k1-1;j>0;j--)
    	    sum2+=a[j];
    	    if(sum1<sum2) 
    	    printf("%d\n",sum1);
    	    else
    	    printf("%d\n",sum2);
    	}
    	return 0;
    }

后来，因为在acm训练期间，学了前缀和、树状数组，觉得这题能写，一交，过了（下面）。

#include<stdio.h>
    int a[100005];
    int main()
    {
    	int i,j,n,m,sum1=0,sum2=0,k1,k2;
    	scanf("%d",&n);
    	for(i=1;i<=n;i++)
    	{
    		scanf("%d",&a[i]);
    		if(i!=1)
    		a[i]+=a[i-1];
    	}
    	a[0]=0;
    	scanf("%d",&m);
    	for(i=0;i<m;i++)
    	{
    		sum1=0;
    		sum2=0;
    		scanf("%d %d",&k1,&k2);
    		if(k1>k2)           //交换 看k1和k2，保证k1<k2 
    		{
    			int temp=k1;
    			k1=k2;
    			k2=temp;
    		}
    		sum1=a[k2-1]-a[k1-1];
    		sum2=a[n]-a[k2-1]+a[k1-1];
    	    if(sum1<sum2) 
    	    printf("%d\n",sum1);
    	    else
    	    printf("%d\n",sum2);
    	}
    	return 0;
    }

## 别人的代码： ##

他用的是循环队列

/*
    ** @Brief:No.1046 of PAT advanced level.
    ** @Author:Jason.Lee
    ** @Date:2018-12-19
    ** @Solution: https://blog.csdn.net/CV_Jason/article/details/85090477
    */
    #include<iostream>
    #include<vector>
    using namespace std;
    
    struct exits{
    	int forward;
    	int backward;
    };
    
    int main(){
    	int N;
    	while(cin>>N){
    		vector<int> distance;
    		vector<exits> alldist(N+1);
    		int input;
    		for(int i=0;i<N;i++){
    			cin>>input;
    			distance.push_back(input);
    		} 
    		int sum = 0,index = 2;
    		for(auto it = distance.begin();it!=distance.end();it++){
    			sum+=*it;
    			alldist[index++].forward = sum;
    		}
    		sum = 0,index = N;
    		for(auto it = distance.rbegin();it!=distance.rend();it++){
    			sum+=*it;
    			alldist[index--].backward = sum;
    		}
    		int M,e1,e2;
    		cin>>M;
    		for(int i=0;i<M;i++){
    			cin>>e1>>e2;
    			if(e1>e2){
    				swap(e1,e2);
    			}
    			int dist1 = alldist[e2].forward - alldist[e1].forward;
    			//cout<<"dist1 = "<<dist1<<endl;
    			int dist2 = alldist[e1].forward + alldist[e2].backward;
    			//cout<<"dist2 = "<<dist2<<endl;
    			cout<<(dist1<dist2? dist1:dist2)<<endl;
    		}
    	}
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190716130506677.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4,size_16,color_FFFFFF,t_70