首页 > 其他 > 详细

1046 Shortest Distance

时间:2019-02-28 15:43:22      阅读:156      评论:0      收藏:0      [点我收藏+]

题目大意是给你一个环上相邻两点之间的距离,问你任意两点间的最短距离。

用前缀和,判断顺着和逆着走哪边小,注意查询点的位置不一定是后面比前面大。水题~

技术分享图片
#include <iostream>
#include <string.h>
using namespace std;
#define maxn 100005

int a[maxn],b[maxn];
int main()
{
    memset(b,0,sizeof(b));
    int n,sum=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    for(int i=1;i<=n;i++)
        b[i]=a[i-1]+b[i-1];
    int q,s,t;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>s>>t;
        if(s>t)
            swap(s,t);
        int tmp=b[t-1]-b[s-1];
        if(tmp<=sum-tmp)
            cout<<tmp<<endl;
        else
            cout<<sum-tmp<<endl;
    }
}
View Code

 

1046 Shortest Distance

原文:https://www.cnblogs.com/FTA-Macro/p/10450690.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!