首页 > 试题广场 >

小美走公路

[编程题]小美走公路

热度指数：2830 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个环形的公路，上面共有 $n$ 站，现在给定了顺时针第 $i$ 站到第 $i+1$ 站之间的距离（特殊的，也给出了第 $n$ 站到第 1 站的距离）。小美想沿着公路第 $x$ 站走到第 $y$ 站，她想知道最短的距离是多少？

输入描述:

第一行输入一个正整数，代表站的数量。
第二行输入个正整数，前个数代表顺时针沿着公路走，站到第站之间的距离；最后一个正整数代表顺时针沿着公路走，第站到第 1 站的距离。·
第三行输入两个正整数和，代表小美的出发地和目的地。

输出描述:

一个正整数，代表小美走的最短距离。

示例1

输入

3
1 2 2
2 3

输出

示例2

输入

3
1 2 2
1 3

输出

算法知识视频讲解

感性的肖恩在做核酸

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int[] nums = new int[n];
        int i = 0;
        long sum = 0;
        for (;i<n;i++) { // 注意 while 处理多个 case
            nums[i] = in.nextInt();
            sum += nums[i];  // 记录全部路程 即一圈的路程
        }
        int start = in.nextInt();
        int end = in.nextInt();
        long counterclockwise = 0; //顺时针需要的路程
        // 由于下面只计算顺时针的路程 因此当开始站点大于结束站点时 做一个反向
        int s = Math.min(start, end);
        int e = Math.max(start, end);

        for(i=s-1; i<e-1; i++){
            counterclockwise += nums[i];
        }
    // 逆时针路程=总路程减去顺时针路程
        System.out.println(Math.min(counterclockwise, sum-counterclockwise));

    }
}

发表于 2023-09-18 20:12:59 回复(1)

Python

牛客39626858号

为什么只过了26/30 ，为什么还有四个过不了？

n=int(input())

list1=list(map(int,input().split()))
a,b=map(int,input().split())
if a>b:
a,b=b,a
ans1=0
ans2=0
for i in range(a,b):
ans1+=list1[i-1]
for i in range(a,2,-1):
ans2+=list1[i-2]
for i in range(n-1,b-2,-1):
ans2+=list1[i]
if ans1<ans2:
print(ans1)
else:
print(ans2)

编辑于 2024-03-25 21:17:43 回复(2)

Python

G了的伊登很胖墩墩

N = int(input())

dis = [int(x) for x in input().split()]

location = [int(y) for y in input().split()]

distance_1 = 0
distance_2 = 0

for i in range(min(location)-1,max(location)-1):
    distance_1 +=  dis[i]
    dis[i] = 0
distance_2 = sum(dis)

print(min(distance_1,distance_2))

编辑于 2023-09-15 19:33:39 回复(0)

C/C++

黄小黄本黄

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

int main() {

    int n;

    scanf("%d", &n);
    vector<int> a(n + 1, 0);
    vector<long long> b(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[i] = b[i - 1] + a[i];
    }

    int x, y;
    scanf("%d %d", &x, &y);

    int result = 0;

    // 顺时针走
    if (y >= x) printf("%lld", min(b[y - 1] - b[x - 1], b[n] - (b[y - 1] - b[x - 1])));
    else printf("%lld", min(b[x - 1] - b[y - 1], b[n] - (b[x - 1] - b[y - 1])));


    return 0;
}

发表于 2023-08-18 14:57:47 回复(0)

C/C++

杰超123

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

int main() {
    int len=0;
    cin>>len;
    vector<long> v(len);
    long sum=0;
    for(int i=0;i<len;i++){
        long num=0;
        cin>>num;
        v[i]=num;
        sum+=num;
    }
    int s,e;
    cin>>s>>e;
    if(s>e) swap(s,e);
    long ans=0;
    for(int i=s;i<e;i++){
        ans+=v[i-1];
    }
    cout<<min(ans,sum-ans);
}

计算两个方向即可

编辑于 2024-08-24 00:09:14 回复(0)

C/C++

牛客911136700号

#include <iostream>
using namespace std;
#include <vector>
int main() {
    int n;
    cin >> n;
    vector<long long> vec(n+2,0);
    vector<long long> cost(n+2,0);
    for(int i = 1; i <= n ; i++)
    { 
        cin >> vec[i];
        cost[i+1]= cost[i]+vec[i];
    }
    int i,j;
    cin>>i>>j;
    if(i>j) swap(i,j);
    long long res = min(cost[j]-cost[i],cost[n+1]-(cost[j]-cost[i]));
    cout<<res<<endl;

}

发表于 2024-08-04 20:28:52 回复(0)

suwueng

这个就是比较顺时针还是逆时针走更近，只要求出一种走法的距离，另外一个一减就行，然后比较、取最小。因为是按顺时针顺序给的点与点的距离，为了不去考虑跨过最后一个节点，可以直接把小的值当起点，大的当终点。

import sys

n = int(input())
lens = list(map(int, input().split()))
len_sum = sum(lens)
x, y = list(map(int, input().split()))

start = min(x, y)
end = max(x, y)
ans = sum(lens[start-1:end-1])
ans = min(ans, len_sum - ans)
print(ans)

编辑于 2024-03-09 21:21:43 回复(0)

ryujin_nimi

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

long long d[N];

int main() {
int n;
cin >> n;
long long sum = 0;
for (int i = 1; i <= n; i ++) {
int a;
cin >> a;
sum += a;
d[i] = sum;
}
int x, y;
cin >> x >> y;
if (x > y) swap(x, y);
long long dist = d[y - 1] - d[x - 1];
if (dist < sum - dist) cout << dist;
else cout << sum - dist;
return 0;
}

编辑于 2024-03-09 00:07:54 回复(0)

牛牛不会牛泪

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n + 1];
        for (int i = 1;  i <= n; i++) {
            a[i] = sc.nextInt();
        }
        int x = sc.nextInt(), y = sc.nextInt();

        if(x > y) {
            int t = x;
            x = y;
            y = t;
        }

        // System.out.println(x + " " + y);   下面的计算都是要保证x < y的情况下考虑的，所以要交换

        long left = 0, right = 0;

        //顺时针走
        for(int i = x; i < y; i++){
            left += a[i];
        }

        //逆时针走
        for(int i = y; i <= n; i++){
            right += a[i];
        }
        for(int j = 1; j < x; j++){
            right += a[j];
        }

        System.out.println(left > right ? right : left);

    }
}

编辑于 2024-02-12 17:25:51 回复(0)

mrk666

核心点，顺+逆走=总的路长

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            in.nextLine();
            String[] strArr = in.nextLine().split(" ");
            String[] xyArr = in.nextLine().split(" ");
            int x = Integer.parseInt(xyArr[0]);
            int y = Integer.parseInt(xyArr[1]);
            int min = Math.min(x,y)-1;
            int max = Math.max(x,y)-1;
            long subSum=0;
            long sum = 0;
            for(int i=0;i<n;i++){
                int num = Integer.parseInt(strArr[i]);
                sum+=num;
                if(i>=min && i<max){
                    subSum+=num;
                }
            }
            System.out.println(Math.min(subSum,sum-subSum));
        }
    }
}

编辑于 2023-12-14 18:59:43 回复(0)

Python

秋招早日上岸

python, 一个环形问题，主要可以分为两条路，一条是正向，一条是反向。第一步利用记录从每个点到原所需的路程。最后只需要找出dis1[y]-dis1[x],sum(arr)-dis1[y]+dis1[x]两个值中的最小值就可以。

def sol(n,arr,x,y):

    if x>=y: 
        x,y = y-1,x-1
    else:
        x,y = x-1,y-1
    dis1 = [0]*n
    for i in range(1,n):
        dis1[i] = arr[i-1]+dis1[i-1]
    return min(dis1[y]-dis1[x],sum(arr)-dis1[y]+dis1[x])

while 1:
    try:
        n = int(input())
        arr = list(map(int,input().split()))
        x,y = map(int,input().split())
        ans = sol(n,arr,x,y)
        print(ans)
    except:
        break

发表于 2023-10-21 02:44:46 回复(0)

Java

Innocence24

import java.util.*;

/**
 * @author ayj
 * @date 2023/9/11
 * @Description 美团2024届秋招笔试第一场编程真题
 */
public class Main {
    private static final Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        question06();
    }

  private static void question06() {
    int n = sc.nextInt();
    long[] preSum = new long[n];
    for (int i = 0; i < n; i++) {
      preSum[i] = sc.nextLong();
      if (i != 0) {
        preSum[i] += preSum[i - 1];
      }
    }
    int x = sc.nextInt() - 1;
    int y = sc.nextInt() - 1;
    if (x > y) {
      x = x ^ y;
      y = x ^ y;
      x = x ^ y;
    }
    long leftDis = x > 0 ? preSum[y - 1] - preSum[x - 1] : preSum[y - 1];
    long rightDis = preSum[n - 1] - preSum[y - 1];
    if(x > 0){
      rightDis += preSum[x - 1];
    }
    System.out.println(Math.min(leftDis, rightDis));
  }
}

发表于 2023-09-12 18:54:03 回复(0)

Java

奶油pao芙

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            Long[] a = new Long[n];
            for(int i = 0; i < n; i++) {
                a[i] = in.nextLong();
            }
            Long x = in.nextLong() - 1;
            Long y = in.nextLong() - 1;
            if(x > y) {
                Long t = x;
                x = y;
                y = t;
            }
            if(x == y) {
                System.out.print(0);
                return;
            }
            Long sum1 = Long.valueOf(0);
            Long sum2 = Long.valueOf(0);
            for(int i = 0; i < n; i++) {
                if((x + i) != y) {
                    sum1 += a[(int) (x + i)];
                }else {
                    break;
                }
            }
            for(int i = 0; i < n; i++) {
                if((y + i) % n != x) {
                    sum2 += a[(int) ((y + i) % n)];
                }else {
                    break;
                }
            }
            System.out.println(Math.min(sum1, sum2));
        }
    }
}

发表于 2023-08-22 16:41:36 回复(0)

一个人生下来就是来工作得

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n; 
    std::cin >> n;

    std::vector<long> distances(n,0); 
    long sum=0;
    for (int i = 0; i < n; ++i) {
        cin>>distances[i];
        sum += distances[i];
    }
    int hi,lo;
    cin>>lo>>hi;
    if(lo>hi){
        swap(lo,hi);
    }

    lo--;hi--;
    long k =0;
    bool flag = 0;
    for(int i=lo;i<hi;++i){
        k += distances[i];
        if(k>=(sum/2+1)){
            flag = 1;
            break;
        }
    }
    
    if(flag){
        k=0;
        for(int i=0;i<lo;++i){
            k+=distances[i];
        }
        for(int i=hi; i<n;++i){
            k+=distances[i];
        }
    }
    cout<<k;
    return 0;
}

发表于 2023-08-19 08:44:13 回复(0)

Python

longkouding

importsys
 
n = sys.stdin.readlines()
num_station = int(n[0])
dist = n[1].strip().split()
mindist = n[2].strip().split()
start = int(mindist[0])
end = int(mindist[1])
res = float("inf")
res2 = float("inf")
res3 = float("inf")
res4 = float("inf")
ifstart > end:
    res2 = 0
    res3 = 0
    fori in range(start-1,num_station):
        res2 += int(dist[i])
    fori in range(0,end-1):
        res2 += int(dist[i])
    start,end = end,start
    fori in range(start-1,end-1):
        res3 += int(dist[i])
else:
    res = 0
    res4 = 0
    fori in range(start-1,end-1):
        res += int(dist[i])
    start,end = end,start
    fori in range(start-1,num_station):
        res4 += int(dist[i])
    fori in range(0,end-1):
        res4 += int(dist[i])
final= min(res,res2,res3,res4)
print(final)

编辑于 2023-08-18 18:34:57 回复(0)

最好的小区的最好的保安_两年内当上队长

package main
 
import (
    "fmt"
)
 
func main() {
    var n int
    fmt.Scan(&n)
 
    dis := make([]int, n)
    for i:=0; i<n; i++ {
        var d int
        fmt.Scan(&d)
        dis[i] = d
    }
 
    var start, end int
    fmt.Scan(&start, &end)
 
    if start > end {
        start, end = end, start
    }
 
    // 正向走
    sumZ := 0
    for i:=start; i<end; i++ {
        sumZ += dis[i-1]
    }
 
    // 反向走
    sumF := 0
    // 1. 从 end 到最后
    for i:=end; i<=n; i++ {
        sumF += dis[i-1]
    }
    // 2. 从 1 到start
    for i:=1; i<start; i++ {
        sumF += dis[i-1]
    }
 
    if sumF < sumZ {
        fmt.Println(sumF)
    } else {
        fmt.Println(sumZ)
    }
}

发表于 2023-08-17 17:13:02 回复(0)

bettyboy

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

int main() {

int N, tmp, x, y;

cin >> N;

vector<int> arr;

arr.resize(N);

for (int i = 0; i < N; ++i) {

cin >> tmp;

arr[i] = tmp;

}

cin >> x >>y;

vector<int64_t> presum;

presum.reserve(N + 5);

presum.push_back(0);

for (int i = 0; i < N - 1; ++i) {

presum.push_back(0LL + arr[i] + presum.back());

}

if (x > y) {

swap(x, y);

}

int64_t len1 = presum[y - 1] - presum[x - 1];

int64_t len2 = presum.back() - presum[y - 1] + presum[x - 1] + arr.back();

cout << min(len1, len2) <<endl;

}

// 64 位输出请用 printf("%lld")

发表于 2023-08-16 23:09:28 回复(0)

提交观点

问题信息

来自：美团2023年秋招笔试...

难度：

17条回答 23收藏 1205浏览

小美走公路

输入描述:

输出描述:

输入

输出

输入

输出

问题信息

热门推荐

相关试题