星空's Blog
PAT-A1046 Shortest Distance

原题

Shortest Distance (20 分)

题解

以输入 n = 5,数据 1 2 4 14 9 为例
创建一个长为n + 1的数组 distance
录入时计算 下标-1 与1的距离
distance[0] = 0; //第1个元素1 与1的距离
distance[1] = 1; //第2个元素2 与1的距离
distance[2] = 3; //第3个元素4 与1的距离
distance[3] = 7; //第4个元素14 与1的距离
distance[4] = 21; //第5个元素19 与1的距离
distance[5] = 30; //圆环总长度

计算 a 和 b 的距离时,取两点到原点距离的差的绝对值
int c = abs(distance[a – 1] – distance[b – a])
因为是个环,所以要和另一方向的距离比较
int d = abs(distance[n] – c)
取距离最短的 min(c,d)

代码

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

int main(void) {
    int n;
    cin >> n;
    int distance[n + 1] = {0};
    for (int i = 0;i < n;i++) {
        int k;
        cin >> k;
        if (i == 0) {
            distance[i + 1] = k;
        } else {
            distance[i + 1] = k + distance[i];
        }
    }
    int q;
    cin >> q;
    for (int i = 0;i < q;i++) {
        int a,b;
        cin >> a >> b;
        int c = abs(distance[a - 1] - distance[b - 1]);
        int d = abs(distance[n] - c);
        cout << min(c,d) << endl;
    }
    return 0;
}
博客所有文章禁止转载。
算法AC代码仅供参考,请不要未经修改直接套用。
首页      算法学习      PAT-A      PAT-A1046 Shortest Distance
https://secure.gravatar.com/avatar/271861a23dcdde929d3ee8cb8c04f854?s=256&d=monsterid&r=g

星空

文章作者

发表评论

textsms
account_circle
email

星空's Blog

PAT-A1046 Shortest Distance
原题 Shortest Distance (20 分) 题解 以输入 n = 5,数据 1 2 4 14 9 为例 创建一个长为n + 1的数组 distance 录入时计算 下标-1 与1的距离 distance[0] = 0; //第1个元素1 与1的距离 dis…
扫描二维码继续阅读
2019-09-01
分类
标签云