小明家的牛误入了一个回旋走廊

回旋走廊
描述

小明家的牛误入了一个回旋走廊，这是一个首尾相连的环形走廊，走廊中有若干个平台，某个平台上有奶牛最爱吃的牧草，现在给出奶牛自己的位置和牧草的位置，请你计算出奶牛到达牧草位置的最短距离

day12-04.zip

输入
第一行一个整数n，表示平台个数
第二行输入n个正整数a，前n−1个数代表朝某个方向走，i平台到第i+1站之间的距离；最后一个正整数代表朝另一个方向走，第n个平台到第1个平台的距离。
第三行输入两个正整数x和y，表示奶牛的位置和牧草的位置。
1≤n≤10^5
1≤a≤10^9
1≤x,y≤n

输出
一个整数，表示最短距离

输入样例 1

3
1 2 2
2 3
输出样例 1

2

#include <iostream>
using namespace std;
int count(int n, int* distances, int cow, int grass) {
    int total = 0;
    int curr = cow;
    while (curr != grass) {
        total += distances[curr - 1];
        curr = (curr % n) + 1;
    }
    return total;
}

int main() {
    int n;
    cin >> n;
    int* distances = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> distances[i];
    }
    int cow, grass;
    cin >> cow >> grass;
    int result = count(n, distances, cow, grass);
    cout << result << endl;
    delete[] distances;
    return 0;
}

计算出所有平台的总距离total，然后从牛到草选一个方向走并计算距离dd，最后判断dd 和（total-dd)哪个小即可。
运行结果：

代码：

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


int main()
{
    int n;
    long long* dis = 0;
    long long total = 0;
    int cur, target;
    cin >> n;
    dis = new long long[n];
    for (int i = 0; i < n; i++)
    {
        cin >> dis[i];
        total += dis[i];
    }
    cin >> cur >> target;
    long long t;
    if (cur > target)
    {
        t = cur;
        cur = target;
        target = t;
    }
    long long dd = 0;
    for (int i = cur; i < target; i++)
        dd += dis[i - 1];

    if (dd < (total - dd))
        cout << dd;
    else
        cout << total - dd;

    delete[] dis;
    dis = 0;
    return 0;
}

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

int main() {
    int n;
    cin >> n;

    vector<int> distances(n);
    for (int i = 0; i < n - 1; ++i) {
        cin >> distances[i];
    }
    cin >> distances[n - 1];

    int x, y;
    cin >> x >> y;

    if (x > y) {
        swap(x, y);  // 确保 x 在 y 的左边
    }

    int totalDistance = 0;
    for (int i = x - 1; i < y - 1; ++i) {
        totalDistance += distances[i];
    }

    int circularDistance = 0;
    for (int i = 0; i < n; ++i) {
        circularDistance += distances[i];
    }
    circularDistance -= totalDistance;

    int shortestDistance = min(totalDistance, circularDistance);
    cout << shortestDistance << endl;

    return 0;
}

【以下回答由 GPT 生成】

首先，我们需要根据输入的数据构建一个环形走廊的图。可以使用邻接表来表示这个图。邻接表是一种图的表示方法，其中每个顶点（平台）对应一个链表，链表中存储的是与该顶点相连的其他顶点（平台）。

接下来，我们可以使用广度优先搜索算法（BFS）来找到奶牛到达牧草位置的最短距离。BFS可以用来解决从一个节点（起始平台）到另一个节点（目标平台）的最短路径问题。

以下是具体的解决方案:

1. 首先，根据输入的平台个数和距离，构建一个邻接表来表示这个环形走廊的图。每个平台对应一个链表。
2. 创建一个空的邻接表。
3. 从第一个到第n-1个平台，依次将每个平台与下一个平台的距离添加到邻接表中对应平台的链表中。
4. 将第n个平台与第一个平台的距离添加到邻接表中对应平台的链表中。

示例代码:

def build_adj_list(n, distances):
    adj_list = [[] for _ in range(n)] # 创建空的邻接表

    for i in range(n-1):
        adj_list[i].append((i+1, distances[i])) # 添加平台和下一个平台的距离到邻接表中对应平台的链表中
    adj_list[n-1].append((0, distances[n-1])) # 添加第n个平台和第一个平台的距离到邻接表中对应平台的链表中

    return adj_list

# 测试
distances = [1, 2, 2]
adj_list = build_adj_list(3, distances)
print(adj_list)
# 输出: [[(1, 1)], [(2, 2)], [(0, 2)]]

1. 使用广度优先搜索算法（BFS）来找到奶牛到达牧草位置的最短距离。
2. 创建一个队列，用于存储待访问的平台。
3. 创建一个数组，用于记录每个平台是否已经被访问过。
4. 将奶牛的位置添加到队列中，并将对应的数组标记为已访问。
5. 进入一个循环，直到队列为空：
   • 从队列中取出一个平台。
   • 遍历该平台的邻接平台：
   • 如果邻接平台未被访问过，则将其添加到队列中，并将对应的数组标记为已访问。
   • 更新距离数组，即将当前平台到邻接平台的距离加上已知的最短距离。
6. 返回距离数组中的牧草位置对应的距离。

示例代码:

from collections import deque

def shortest_distance(adj_list, cow_pos, grass_pos):
    n = len(adj_list)
    queue = deque()
    visited = [False] * n
    distances = [float('inf')] * n

    queue.append(cow_pos)
    visited[cow_pos] = True
    distances[cow_pos] = 0

    while queue:
        current = queue.popleft()
        for neighbor, distance in adj_list[current]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True
                distances[neighbor] = distances[current] + distance

    return distances[grass_pos]

# 测试
adj_list = [[(1, 1)], [(2, 2)], [(0, 2)]]
cow_pos = 2
grass_pos = 1
print(shortest_distance(adj_list, cow_pos, grass_pos))
# 输出: 2

以上就是解决这个问题的具体步骤和代码。这个方案首先构建了一个环形走廊的图，然后使用广度优先搜索算法来找到奶牛到达牧草位置的最短距离。

【相关推荐】

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7728350
• 除此之外, 这篇博客: 回溯法与分支限界法的总结中的 在当前节点（扩展节点）处，先生成其所有的子节点（分支），然后再从当前的活节点（当前节点的子节点）表中选择下一个扩展节点。为了有效地选择下一个扩展节点，加速搜索的进程，在每一个活节点处，计算一个函数值（限界），并根据函数值，从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。分支限界法解决了大量离散最优化的问题。 部分也许能够解决你的问题。