首页 > 试题广场 >

Shortest Distance (20)

[编程题]Shortest Distance (20)
  • 热度指数：2981 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
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.

输入描述:
Each input file contains one test case.  For each case, the first line contains an integer N (in [3, 105]), followed by N integer distances D1 D2 ... DN, where Di is the distance between the i-th and the (i+1)-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 (<=104), 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 107.


输出描述:
For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.
示例1

输入

5 1 2 4 14 9
3
1 3
2 5
4 1

输出

3
10
7
算法知识视频讲解
添加回答
OFShare头像 OFShare 
//前缀和。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,m,tot,sum[maxn]; 
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&sum[i]);tot+=sum[i];
        sum[i]+=sum[i-1];
    }
    scanf("%d",&m);
    for(int i=1,x,y;i<=m;++i){
        scanf("%d %d",&x,&y);
        if(x>y) swap(x,y);
        printf("%d\n",min(sum[y-1]-sum[x-1],tot-(sum[y-1]-sum[x-1])));
    }
    return 0;
} 

发表于 2018-03-10 00:11:10 回复(0)
风蚀流云头像 风蚀流云 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int exits[N],sum[N];
int main(){
    int n,m,a,b;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d",&exits[i]),sum[i] = sum[i-1] + exits[i];
    scanf("%d",&m);
    while(m--){
        scanf("%d%d",&a,&b);
        if(a>b) swap(a,b);
        printf("%d\n",min(sum[b-1]-sum[a-1],sum[n]-(sum[b-1]-sum[a-1])));
    }
    return 0;
}

发表于 2019-04-01 12:38:25 回复(0)
C/C++
BlackCarDriver头像 BlackCarDriver
/*
https://www.nowcoder.com/questionTerminal/3432b59d01834e53bda8f5eb439bed9b
Shortest Distance (20)  2018-12-18
General mean: give you a circle make up with n node and n-1 edge, you know the length of each edge, require the
shorter distant from node a to node b...
Result: Cost me about 20 minue. Ti is a simple problem too, the first times i see the question, I want to use a bothway
list or use tow arry to record the distant of each node by forward and backward. But it is not easy, so later I find the
rule  that if you know forward-distant, then you can use the total length to subtract it and get backward-distatn, In that
way the proplem become very simple!
 */
const int maxn = 100009;
int dis[maxn];

int main(){
int n, m,t1,t2;
int sum = 0;    //total length of the circle
cin >> n;        //I want to use scanf() firstly, but complier report a error!
for (int t,i = 2; i <= n+1; i++){
cin >> t;
sum += t;
dis[i] = dis[i - 1] + t;
}
cin >> m;
while (m--){
cin >> t1 >> t2;
if (t1 > t2) swap(t1, t2);
printf("%d\n", min(dis[t2]-dis[t1] , sum - (dis[t2] - dis[t1])));
}
return 0;
}

编辑于 2018-12-18 11:13:48 回复(0)
kestars头像 kestars 
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] dis=new int[n];
        for(int i=0;i<n;i++){
            dis[i]=sc.nextInt();
        }
        int m=sc.nextInt();
        for(int i=0;i<m;i++){
            int start=sc.nextInt()-1;
            int end=sc.nextInt()-1;
            if(start>end){
                int temp=start;
                start=end;
                end=temp;
            }
            int total1=0;
            for(int j=start;j<end;j++){
                total1+=dis[j];
            }
            int total2=0;
            for(int j=start-1;j>=0;j--){
                total2+=dis[j];
            }
            for(int j=end;j<n;j++){
                total2+=dis[j];
            }
            if(total1>total2){
                total1=total2;
            }
            System.out.println(total1);
        }
    }
}

发表于 2018-10-05 00:28:25 回复(0)
C/C++
nbgao头像 nbgao 
#include <iostream> 

using namespace std;

const int MAXN = 1000007;
int a[MAXN] = {0};

int main()
{     int n,m,sum=0;     cin>>n;     for(int i=1;i<=n;i++)     {         cin>>a[i];         sum += a[i];     }     cin>>m;     for(int i=1;i<=m;i++)     {         int x,y,start,end,s=0;         cin>>x>>y;         start = min(x,y);         end = max(x,y);         for(int j=start;j<end;j++)             s += a[j];         cout<<min(s, sum-s)<<endl;     }     return 0;
}

发表于 2018-03-14 01:09:35 回复(0)
LiuTaw头像 LiuTaw
用了一个循环链表做的，然后出现了段错误，难道结构体太多了？？？
#include<stdio.h>

#include<cstring>

#include<iostream>

using namespace std;

struct Exit

{

    Exit *right;

    Exit *left;

    int id;

    int leftdis;

    int rightdis;

};

int main()

{

    int N,N1;

    scanf("%d",&N);

    Exit* input[10010];

    int dis[10010];

    for(int i=1;i<N+1;i++)

    {

        int tmp;

        scanf("%d",&tmp);

        dis[i]=tmp;

        Exit *exit = new Exit;

        exit->id = i;

        if(i!=1)

        {

            exit->left = input[i-1];

            exit->left->right = exit;

            exit->left->rightdis =dis[i-1];

            exit->leftdis = dis[i-1];

        }

        input[i] = exit;

        if(i==N)

        {

            exit->right = input[1];

            exit->rightdis = tmp;

            input[1]->left = exit;

            input[1]->leftdis = tmp;

        }

    }

    scanf("%d",&N1);

    for(int i=0;i<N1;i++)

    {

        int a,b;

        scanf("%d %d",&a,&b);

        

        

        Exit *left = input[a]->left;

        Exit *right = input[a]->right;

        int left_total=input[a]->leftdis,right_total=input[a]->rightdis;

        while(1)

        {

            if(left->id==b)

            {

                break;

            }

            left_total+=left->leftdis;

            left = left->left;

        }


        while(1)

        {

            if(right->id==b)

            {

                break;

            }

            right_total+=right->rightdis;

            right = right->right;

        }

        if(left_total>right_total)

            cout<<right_total<<endl;

        else 

            cout<<left_total<<endl;

    }

    return 0;

}

发表于 2018-03-08 15:14:41 回复(1)
C/C++
猫猫猫1头像 猫猫猫1 
#include<bits/stdc++.h>
using namespace std;

const int Max=1e5+10;

int main(){
	int n,dis[Max],total;
	while(cin>>n){
		for(int i=1;i<=n;i++){
			cin>>dis[i];
			total+=dis[i];
			dis[i]+=dis[i-1];
		}
		int m;
		cin>>m;
		while(m--){
			int x,y;
			cin>>x>>y;
			if(x>y) swap(x,y);
			cout<<min(dis[y-1]-dis[x-1],total-dis[y-1]+dis[x-1])<<endl;
		}
	}
	return 0;
}

发表于 2022-11-03 13:50:30 回复(0)
C/C++
牛客160854074号头像 牛客160854074号
#include<stdio.h>
int main()
{
int n,m,x,a,b,t,sum=0,i;
int s=0;
int d[100005];
int min[100005]={0};
int k[100005]={0};
scanf("%d",&n);
for(i=1;i<=n;i++)
{scanf("%d",&d[i]);s=s+d[i];k[i]=s;
}scanf("%d",&m);
for(x=1;x<=m;x++)
{scanf("%d %d",&a,&b);
if(a>b){t=a;a=b;b=t;
}

sum=k[b-1]-k[a-1];

    if(s-sum>sum){min[x]=sum;
    }
    else{min[x]=s-sum;
    }

}
for(i=1;i<=m;i++)
       printf("%d\n",min[i]);
   return 0;
}

发表于 2020-08-15 19:26:15 回复(0)
再不中奖就吃屎头像 再不中奖就吃屎
前缀和 
//Shortest Distance (20分)
#include <iostream>

using namespace std;
int n, m, exits[100001];

int main() {
    exits[0] = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> exits[i];
        exits[i] += exits[i - 1];
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        int x, y, sum1 = 0, sum2 = 0;
        cin >> x >> y;
        int n1 = (x < y) ? x : y;
        int n2 = (x < y) ? y : x;
        sum1 = exits[n2 - 1] - exits[n1 - 1];
        sum2 = exits[n] - exits[n2 - 1] + exits[n1 - 1];
        if (sum1 > sum2) cout << sum2 << endl;
        else cout << sum1 << endl;
    }
}

发表于 2020-03-11 17:43:56 回复(0)
gangstar头像 gangstar 
#include<iostream>
#include<stdlib.h>
#include<algorithm>
#include<vector>
using namespace std;

int main() {
    int n = 0, m = 0,sum = 0,tem = 0,x = 0, y = 0;
    cin >> n;
    vector<int> dis(n + 1);//保存从1到i+1的距离
    for (int i = 1; i <= n; i++) {
        scanf("%d",&tem);
        sum += tem;
        dis[i] = sum;
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        scanf("%d%d",&x,&y);//因为是环形的，故x-y与y-x的距离是一样的
        if (x > y) {
            swap(x, y);
        }
        int len = dis[y - 1] - dis[x - 1];
        printf("%d\n",min(len,sum-len));//整个环形的路径是一定的，从正的距离是一定的，反向的距离也是一定，故比较之后即可以得最小
    }
    system("pause");
    return 0;
}
发表于 2019-10-21 19:42:45 回复(0)
hhhhh.头像 hhhhh.
求助！！答案正确但一直报段错误，实在找不到错在哪里了。。。 
#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 1000000000;

int n;

int main(){
    cin >> n;
    int G[n][n];
    fill(G[1],G[1] + n * n,INF);
    
    
    for(int i = 1;i <= n - 1;i++ ){
        int w;
        cin >> w;
        G[i][i + 1] = w;
        G[i + 1][i] = w;
        
    }
    
    int w;
    cin >> w;
    
        G[n][1] = w;
        G[1][n] = w;
      
    int k;
    cin >> k; 
    for(int l = 1;l <= n;l++){
       for(int i = 1;i <= n;i++){
           for(int j = 1;j <= n;j++){
               if(G[i][l] != INF && G[l][j] != INF && G[i][l] + G[l][j] < G[i][j])
               G[i][j] = G[i][l] + G[l][j];
           }
       }
   }
    for(int i = 0;i < k;i++){
        int x,y;
        
       cin >> x >> y;
        cout << G[x][y] << endl;
    }
    return 0;
}

发表于 2019-08-31 07:13:24 回复(0)
C/C++
Fingers°头像 Fingers° 

	/*





	求得环的总长度dis，算出单向距离的dis1, dis2 = dis- di1。取短即可。





	*/





	





	#include<iostream>





	 





	usingnamespacestd;





	 





	 





	intmain()





	{





	    intn;





	    while(cin >> n)





	    {





	        intd[n];





	        intdis = 0;





	        for(inti = 0 ; i < n;i++)





	        {





	            cin >> d[i];





	            dis += d[i];





	        }





	        intn1;





	        cin >> n1;





	        intd1, d2;





	        for(inti = 0 ;i < n1;i++)





	        {





	            cin >> d1>> d2;





	            if(d1 > d2)





	            {





	                intt = d1;





	                d1 = d2;





	                d2 = t;





	            }





	            intdis1 = 0, dis2;





	            for(inti = d1-1; i < d2 - 1; i++)





	            {





	                dis1 += d[i];





	            }





	             





	            dis2 = dis - dis1;





	             





	            if(dis1 < dis2)





	            {





	                cout << dis1<<endl;





	            }else





	            {





	                cout<< dis2 <<endl;





	            }





	        }





	    }





	    return0;





	}

发表于 2019-07-14 10:27:09 回复(0)
Emptycity°头像 Emptycity°
先算出这个环的总长度，两个点之间只可能有两条路，所以只要求出其中一条，就可以知道另外一条的距离。所以需要判断输入的起点和终点的大小，终点小则将其进行交换，我们可以通过循环简单算出两个点之间从小数字的起点到大数字的终点之间的距离，然后用环长度减一下，比较两个大小即可
#include <stdio.h> const int N = 100010; int main(){     int n, m, start, stop, total = 0, len;     int a[N];     scanf("%d", &n);     a[0] = 0;     for(int i = 1; i <= n; i++){         scanf("%d", &a[i]);         total += a[i];     }     scanf("%d", &m);     while(m--){         len = 0;         scanf("%d%d", &start, &stop);         if(start > stop) {             int temp = start;             start = stop;             stop = temp;         }         for(int i = start; i < stop; i++){             len += a[i];         }         if(len < (total - len)) printf("%d\n", len);         else printf("%d\n", total - len);     } }

发表于 2019-07-04 20:34:37 回复(0)
11122222222222222222头像 11122222222222222222
D=map(int,raw_input().split())
n=int(raw_input())
pairs=[map(int,raw_input().split()) for _ in range(n)]
dis,cdis=[0]*D[0],sum(D[1:])
for i in range(1,len(dis)):
    dis[i]=dis[i-1]+D[i]
for i,j in pairs:
    print min(abs(dis[j-1]-dis[i-1]),cdis-abs(dis[j-1]-dis[i-1]))
由于它构成了环，所以每对结点只有两个方向走，顺时针和逆时针，这里定义dis[i]是从1到I的距离，cdis是环的总距离，只要比较两个方向的距离，那个小就输出哪个即可，这是一道水题

发表于 2019-01-18 16:57:44 回复(0)
Disconnect头像 Disconnect 
from itertools import accumulate
lstin = list(map(int,input().split()))
n,num = int(lstin[0]),list(accumulate(lstin[1:]))
m = int(input())
x = []
for i in range(0,m):
    x = sorted(map(int,input().split()))
    a,b = x[0]-2,x[1]-2
    if a<0:
        y=0
    else:
        y = num[a]
    one = num[b]-y
    two = num[len(num)-1] - one
    print(min(one,two))

发表于 2018-11-23 10:31:56 回复(1)
酒千觞头像 酒千觞 
L=[0]+list(map(int,input().split()[1:]))
M=int(input())
for i in range(1,len(L)):
    L[i]+=L[i-1]
query=[map(int,input().split()) for _ in range(M)]
for a,b in query:
    a,b=min(a,b),max(a,b)
    print(min(L[b-1]-L[a-1],L[a-1]+L[-1]-L[b-1]))

发表于 2018-09-03 22:11:42 回复(0)
C/C++
Caffeine头像 Caffeine 
思路左边加上右边，然后比较大小然后输出
#include <iostream>
#include <vector>
#include <fstream>
#include <math.h>
using namespace std;

#ifdef Debug
ifsteram cin("case.txt");
#endif

long long FindDistance(int & point1, int & point2, vector<int> & v)
{
    int min = point1 > point2 ? point2 : point1;
    int max = point1 > point2 ? point1 : point2;
    long long leftToRight = 0;
    long long rightToLeft = 0;
    // 同时从两个方向出发，寻找最近的路径
    bool find1 = false;
    bool find2 = false;
    for (int i = 0; i + min < max; i++)
    {
        leftToRight += v[i + min];
    }
    for (int i = 0; min - i - 1 + v.size()  != max; i++)
    {
        if (min - i - 1 >= 1)
            rightToLeft += v[min - i - 1];
        else
            rightToLeft += v[min - i - 1 + v.size() - 1];
    }
    //cout << leftToRight << " " << rightToLeft << endl;
    return leftToRight >= rightToLeft ? rightToLeft : leftToRight;
}



int main()
{

    int n;
    cin >> n;
    vector<int> v(n+1);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i+1];
    }
    int m;
    int point1, point2;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> point1 >> point2;
        if (point1 == point2)
            cout << 0 << endl;
        else
            cout << FindDistance(point1, point2, v) << endl;
    }
    system("pause");
}

发表于 2018-08-25 21:07:32 回复(0)
快乐的山顶洞人头像 快乐的山顶洞人 
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {

    int n, m;
    cin >> n;
    vector<int> graph(n+1,0);
    int t;
    for (int i = 0; i < n; i++) {
        cin >> t;
        graph[(i+1)]=graph[i]+t;

    }

    cin >> m;
    int start, last;
    for (int i = 0; i < m; i++) {
        cin >> start >> last;
        if(start>last){
            int temp = start;
            start = last;
            last = temp;
        }
        //cout<<start<<","<<last;
        int dis1 =graph[last-1]-graph[start-1];
        int dis2 = graph[n]-graph[last-1]+graph[start-1];
        int res =min(dis1,dis2);
        cout <<res << endl;
    }
    system("pause");
    return 0;
}
编辑于 2018-07-19 13:58:00 回复(0)
袁博文202头像 袁博文202 
from itertools import accumulate
nd = list(map(int, input().split()))
n, d = nd[0], list(accumulate(nd[1:]))
m = int(input())
tot = d[-1]
for i in range(m):
    line = sorted(map(int,input().split()))
    x, y = line[0]-2, line[1]-2
    dis = d[y] - d[x] if x >= 0 else d[y]
    print(min(dis, tot-dis))

发表于 2018-04-19 16:33:35 回复(0)
C/C++
尼米茨的风头像 尼米茨的风 
#include <cstdio> int main(){ int dis[100010] = {0},shortestDis[100010], point, totalDis = 0;
  scanf("%d", &point); for(int i = 1;i <= point;i++){ int distance;
    scanf("%d", &distance);
    dis[i] =dis[i-1] + distance;
    totalDis += distance;
  } int num;
  scanf("%d", &num); for(int i = 0;i < num;i++){ int a, b;
    scanf("%d%d", &a, &b); if(a > b){ int temp = a;
      a = b;
      b = temp;
    } int abDis = dis[b-1] - dis[a-1]; int remainDis = totalDis - abDis; if(abDis > remainDis)
      shortestDis[i] = remainDis; else shortestDis[i] = abDis;
  } for(int i = 0;i < num;i++){
    printf("%d\n", shortestDis[i]);
  } return 0;
}
发表于 2018-02-26 12:35:36 回复(0)
提交观点

问题信息

编程基础 数组
难度：
26条回答 14152浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号