PAT Advanced 1046 Shortest Distance (20 分) (知识点:贪心算法)

PAT Advanced 1046 Shortest Distance (20 分) (知识点:贪心算法)
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码  

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说PAT Advanced 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]), followed by N integer distances D1​​ D2​​ ⋯ DN​​, where Di​​ is the distance between the i-th and the (-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 (≤), 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 1.

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 <iostream>
using namespace std;
int main()
{
    /**
    该方法运行超时
    */
    int N,M,startNum,endNum,sum1,sum2,tmp;
    cin>>N;
    int graphic[N];//数组模拟简单图
    for(int i=0;i<N;i++){
        cin>>graphic[i];
    }
    cin>>M;
    while(M--){
        sum1=0;sum2=0;
        cin>>startNum>>endNum;
        startNum--;endNum--;
        if(startNum>endNum){
            tmp=startNum;
            startNum=endNum;
            endNum=tmp;
        }
        for(int i=0;i<N;i++){
            if(i>=startNum&&i<endNum) sum1+=graphic[i];
            else sum2+=graphic[i];
        }
        cout<<(sum1>sum2?sum2:sum1)<<endl;
    }
    /**
    读题:
    input
    N个数 Dn为第i和i+1的出口距离,最后一个数是和第一个数的距离
    M行 每行是出口
    */
    system("pause");
    return 0;
}

优化后:

#include <iostream>
using namespace std;
int main()
{
    /**
    查阅参考https://www.jianshu.com/p/cb54521fda65
    可以使用贪心算法
    在输入的同时计算每个点到第一个点的距离,
    并将它存放在数组dis中。两点的距离要么环
    的劣弧,要么是环的优弧,这里先固定一下即
    求由a到b的距离(a<b),另一端距离用总round
     trip distance(圆环总长度)减去这里求的距离,比较两者取最小值,特别地,总距离程序中用虚拟的第n+1点表示,因为它到第一个点的距离恰好等于圆环长度。
   */
    int N,M,sum,A,B,tmp,shortDistance1,shortDistance2;
    cin>>N;int distance[N]={
   0};
    for(int i=0;i<N;i++){
        cin>>distance[i];
        if(i!=0) distance[i]+=distance[i-1];//每次计算总长
        sum=distance[i];
    }
    cin>>M;
    while(M--){
        /**这边比我之前少了一个复杂度*/
        cin>>A>>B;
        A--;B--;
        if(A>B){
            tmp=A;
            A=B;
            B=tmp;
        }
        shortDistance1=(B-1==-1?0:distance[B-1])-(A-1==-1?0:distance[A-1]);
        shortDistance2=sum-shortDistance1;
        cout<<(shortDistance1>shortDistance2?shortDistance2:shortDistance1)<<endl;
    }
    system("pause");
    return 0;
}

 

转载于:https://www.cnblogs.com/littlepage/p/11273781.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29584

发表评论