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=;i<N;i++){
cin>>graphic[i];
}
cin>>M;
while(M--){
sum1=;sum2=;
cin>>startNum>>endNum;
startNum--;endNum--;
if(startNum>endNum){
tmp=startNum;
startNum=endNum;
endNum=tmp;
}
for(int i=;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 ;
}

优化后：

#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]={};
for(int i=;i<N;i++){
cin>>distance[i];
if(i!=) distance[i]+=distance[i-];//每次计算总长
sum=distance[i];
}
cin>>M;
while(M--){
/**这边比我之前少了一个复杂度*/
cin>>A>>B;
A--;B--;
if(A>B){
tmp=A;
A=B;
B=tmp;
}
shortDistance1=(B-==-?:distance[B-])-(A-==-?:distance[A-]);
shortDistance2=sum-shortDistance1;
cout<<(shortDistance1>shortDistance2?shortDistance2:shortDistance1)<<endl;
}
system("pause");
return ;
}