[PAT解题报告] Shortest Distance
给定一个环(高速公路),上面有n个点,每个点到下一个点的距离已知,问任意两点间的最短距离。
简单题,因为时一个环,从x到y的距离(x < y)可以从x正向走到y,也可以从y正向走到x,两者取最小就可以了。至于距离计算可以用“前缀和”。用sum[i]表示前i个点的距离和,其实也是“原点”到达第i个点的距离,或者理解为第i个点在圆上的坐标。下标从1开始,规定sum[0] = 0,那么x到y的距离 (x < y)可能是sum[y - 1] - sum[x - 1],也可能是sum[n] - (sum[y - 1] - sum[x - 1]),原因就是这是一个圈,距离可以两个方向算,总和恰好是圈长。这两者取最小就可以了。

代码:
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

int sum[100005];
int main() {
int n;
    scanf("%d",&n);
    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d",&x);
        sum[i] = x + sum[i - 1];
    }
    int m;
    scanf("%d",&m);
    for (;m;--m) {
        int x,y;
        scanf("%d%d",&x,&y);
        int temp = sum[max(x,y) - 1] - sum[min(x,y) - 1];
        printf("%d\n",min(temp, sum[n] - temp));
    }
    return 0;
}

原题链接: http://www.patest.cn/contests/pat-a-practise/1046


注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
2022-12-29 23:08
浙江大学_2021
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-28 10:16
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-16 02:48
门头沟学院_2022
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议