【算法训练营】最小交换，楼尔邦德，最短路（python实现）

本文主要是介绍【算法训练营】最小交换，楼尔邦德，最短路（python实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

3
3 2 1

3

代码实现 

def merge_and_count(arr, left, mid, right):i, j, k = left, mid + 1, 0count = 0temp = [0] * (right - left + 1)while i <= mid and j <= right:if arr[i] <= arr[j]:temp[k] = arr[i]i += 1else:temp[k] = arr[j]count += mid - i + 1  # 计算逆序对数量j += 1k += 1while i <= mid:temp[k] = arr[i]i += 1k += 1while j <= right:temp[k] = arr[j]j += 1k += 1for i in range(len(temp)):arr[left + i] = temp[i]return countdef merge_sort_and_count(arr, left, right):count = 0if left < right:mid = (left + right) // 2count += merge_sort_and_count(arr, left, mid)count += merge_sort_and_count(arr, mid + 1, right)count += merge_and_count(arr, left, mid, right)return countdef min_swaps(arr):return merge_sort_and_count(arr, 0, len(arr) - 1)# 读取输入
n = int(input())
arr = list(map(int, input().split()))# 计算最少花费的元钱
result = min_swaps(arr)
print(result)

3
3 2 5
6
1
2
3
4
5
6

2
2
3
5
5
-1

 代码实现

def binary_search(arr, target):low, high = 0, len(arr) - 1result = -1while low <= high:mid = (low + high) // 2if arr[mid] >= target:result = arr[mid]high = mid - 1else:low = mid + 1return resultdef main():# 读取输入n = int(input())sequence = list(map(int, input().split()))q = int(input())# 对序列进行排序sorted_sequence = sorted(sequence)# 处理每个查询for _ in range(q):x = int(input())# 使用二分查找找到不小于 x 的最小整数result = binary_search(sorted_sequence, x)# 输出答案print(result)if __name__ == "__main__":main()

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

7

代码实现 

import heapqdef dijkstra(graph, start, end):n = len(graph)dist = [float('inf')] * ndist[start - 1] = 0pq = [(0, start)]while pq:curr_dist, node = heapq.heappop(pq)if curr_dist > dist[node - 1]:continuefor neighbor, weight in graph[node]:new_dist = curr_dist + weightif new_dist < dist[neighbor - 1]:dist[neighbor - 1] = new_distheapq.heappush(pq, (new_dist, neighbor))return dist[end - 1]# 读取输入
n, m, s, t = map(int, input().split())
graph = {i: [] for i in range(1, n + 1)}for _ in range(m):u, v, w = map(int, input().split())graph[u].append((v, w))graph[v].append((u, w))# 调用 Dijkstra 算法求最短路径
result = dijkstra(graph, s, t)# 输出结果
print(result)

这篇关于【算法训练营】最小交换，楼尔邦德，最短路（python实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！