PAT-A1046題解

更多的請檢視我的個人部落格:https://beatjerome.github.io

PAT-A1046. Shortest Distance (20)

【時間限制】

100 ms

【記憶體限制】

65536 kB

【代碼長度限制】

16000 B

【Abstract】

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

題目的意思大緻是：

給你n個結點兩兩之間的距離。

然後進行m次查詢，每次查詢給你2個結點。求最短距離。

錯誤代碼示範：

錯誤的原因主要在于太過暴力。完全沒有考慮到時間複雜度。在這麼大的時間複雜度下是不可能在Limit 100ms下跑完的。是以此代碼還需要進行一些處理。

#include<iostream>
using namespace std; 
const int MAXN=;
int main(){
    int n;
    int m;                  //查詢次數 
    int a,b;                //查詢的結點
    int D1=;
    int D2=;               //不同方向計算的距離  
    int Distance[MAXN];
    int temp;
    cin>>n;
    for(int i=;i<n;i++){   //讀入結點之間距離 
        cin>>Distance[i];
    }
    cin>>m;
    for(int i=;i<m;i++){
        D1=;               //清零操作 
        D2=;
        cin>>a>>b;
        if(a>b){
            temp=a;
            a=b;
            b=temp;
        }
        for(int j=a-;j<=b-;j++){
            D1+=Distance[j];
        }
        for(int j=b-;j<n;j++){
            D2+=Distance[j];
        } 
        for(int j=;j<a-;j++){
            D2+=Distance[j];
        }
        if(D1>D2)
            cout<<D2;
        else
            cout<<D1;
        if(i!=m-)
            cout<<endl;
    } 
    return ; 
} 
           

AC代碼：

#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN=;
int dis[MAXN],A[MAXN];  //dis數組表示1結點順時針到達i結點的距離

int main(){
    int sum=,m,n,left,right;
    cin>>n;
    for(int i=;i<=n;i++){
        cin>>A[i];
        sum+=A[i];      //累加數組 
        dis[i]=sum;     //預處理dis數組 
    }
    cin>>m;
    for(int i=;i<m;i++){
        cin>>left>>right;
        if(left>right)
            swap(left,right);
        int temp=dis[right-]-dis[left-];
        cout<<min(temp,sum-temp)<<endl;
    }
    return ;
}