def merge(arr, left, mid, right):
    # 原地合并过程
    start = left
    end = mid + 1

    # 合并两个部分
    while start <= mid and end <= right:
        if arr[start] <= arr[end]:
            start += 1
        else:
            value = arr[end]
            index = end
            while index != start:
                arr[index] = arr[index - 1]
                index -= 1
            arr[start] = value
            
            # 更新所有指针
            start += 1
            mid += 1
            end += 1
            
def merge_sort(arr, left, right):
    if left < right:
        mid = (left + right) // 2
        merge_sort(arr, left, mid)
        merge_sort(arr, mid + 1, right)
        merge(arr, left, mid, right)

# 测试
arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr, 0, len(arr) - 1)
print(arr)  # 输出：[3, 9, 10, 27, 38, 43, 82]

def partition(arr, low, high):
    mid = low + (high - low) // 2
    pivot = sorted([arr[low], arr[mid], arr[high]])[1]  # 选择中位数作为基准
    pivot_index = arr.index(pivot)

    # 移动基准到末尾
    arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
    
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

# 测试
arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr, 0, len(arr) - 1)
print(arr)  # 输出：[1, 5, 7, 8, 9, 10]

def bucket_sort(array):
    if len(array) == 0:
        return array

    # 1. 创建桶
    min_value = min(array)
    max_value = max(array)
    bucket_count = max_value - min_value + 1
    buckets = [[] for _ in range(bucket_count)]

    # 2. 分配数据
    for num in array:
        buckets[num - min_value].append(num)

    # 3. 桶内排序及合并
    sorted_array = []
    for bucket in buckets:
        if bucket:
            sorted_array.extend(sorted(bucket))  # 使用内置的 sorted 函数

    return sorted_array

# 示例
data = [3, 6, 2, 8, 4, 5, 7, 1]
print(bucket_sort(data))

def counting_sort_on_digit(array, exp):
    output = [0] * len(array)
    count = [0] * 10

    # 统计每个数字出现的频次
    for num in array:
        index = (num // exp) % 10
        count[index] += 1

    # 更新计数数组
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 构建输出数组
    for i in range(len(array) - 1, -1, -1):
        index = (array[i] // exp) % 10
        output[count[index] - 1] = array[i]
        count[index] -= 1

    return output

def radix_sort(array):
    max_value = max(array)
    exp = 1  # 初始化为个位

    while max_value // exp > 0:
        array = counting_sort_on_digit(array, exp)
        exp *= 10

    return array

# 示例
data = [170, 45, 75, 90, 802, 24, 2, 66]
print(radix_sort(data))

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 示例图
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'D': 1},
    'C': {'A': 4, 'D': 3},
    'D': {'B': 1, 'C': 3}
}

print(dijkstra(graph, 'A'))  # 输出从A到各点的最短距离

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    
    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])  # 路径压缩
        return self.parent[u]
    
    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu != pv:
            self.parent[pu] = pv

def kruskal(vertices, edges):
    uf = UnionFind(len(vertices))
    mst = []
    edges.sort(key=lambda x: x[2])  # 按权重排序
    
    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, weight))
    
    return mst

# 示例数据
vertices = [0, 1, 2, 3]
edges = [(0, 1, 1), (1, 2, 2), (2, 3, 1), (0, 3, 3), (1, 3, 2)]
mst = kruskal(vertices, edges)
print("最小生成树的边:", mst)

import heapq

def prim(vertices, edges):
    graph = {v: [] for v in vertices}
    for u, v, weight in edges:
        graph[u].append((weight, v))
        graph[v].append((weight, u))
    
    mst = []
    visited = {vertices[0]}  # 从第一个顶点开始
    edges_heap = graph[vertices[0]]
    heapq.heapify(edges_heap)
    
    while edges_heap:
        weight, u = heapq.heappop(edges_heap)
        if u not in visited:
            visited.add(u)
            mst.append((vertices[0], u, weight))  # 记录边
            for weight, v in graph[u]:
                if v not in visited:
                    heapq.heappush(edges_heap, (weight, v))
    
    return mst

# 示例数据
vertices = [0, 1, 2, 3]
edges = [(0, 1, 1), (1, 2, 2), (2, 3, 1), (0, 3, 3), (1, 3, 2)]
mst = prim(vertices, edges)
print("最小生成树的边:", mst)

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)  # 存储图的结构
        self.capacity = {}               # 存储边的容量

    def add_edge(self, u, v, cap):
        self.graph[u].append(v)
        self.graph[v].append(u)  # 创建反向边
        self.capacity[(u, v)] = cap
        self.capacity[(v, u)] = 0  # 初始化反向边的容量为 0

    def bfs(self, s, t, parent):
        visited = set()
        queue = deque([s])
        visited.add(s)

        while queue:
            u = queue.popleft()

            for v in self.graph[u]:
                if v not in visited and self.capacity[(u, v)] > 0:
                    visited.add(v)
                    parent[v] = u
                    queue.append(v)

        return t in visited

    def ford_fulkerson(self, s, t):
        parent = {}
        max_flow = 0

        while self.bfs(s, t, parent):
            path_flow = float('Inf')
            v = t

            while v != s:
                u = parent[v]
                path_flow = min(path_flow, self.capacity[(u, v)])
                v = parent[v]

            v = t
            while v != s:
                u = parent[v]
                self.capacity[(u, v)] -= path_flow
                self.capacity[(v, u)] += path_flow
                v = parent[v]

            max_flow += path_flow

        return max_flow

# 使用示例
g = Graph()
g.add_edge('s', 'A', 10)
g.add_edge('s', 'B', 5)
g.add_edge('A', 'C', 10)
g.add_edge('B', 'C', 15)
g.add_edge('C', 't', 10)

max_flow = g.ford_fulkerson('s', 't')
print(f"最大流为: {max_flow}")

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(capacity + 1):
            if j < weights[i-1]:
                dp[i][j] = dp[i-1][j]  # 不放入物品
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1])  # 放入物品
                
    return dp[n][capacity]

# 示例
weights = [1, 2, 3]
values = [10, 15, 40]
capacity = 6
print(knapsack(weights, values, capacity))  # 输出 55

def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0:
                dp[i][j] = j  # 如果word1为空，需要j次插入
            elif j == 0:
                dp[i][j] = i  # 如果word2为空，需要i次删除
            else:
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]  # 字符相同，不需要操作
                else:
                    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)  # 取三者最小
                
    return dp[m][n]

# 示例
word1 = "horse"
word2 = "ros"
print(min_distance(word1, word2))  # 输出 3

def fibonacci(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

def fibonacci_optimized(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

def lcs(A, B):
    m, n = len(A), len(B)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    return dp[m][n]

def knapsack(weights, values, capacity):
    n = len(values)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(capacity + 1):
            if j < weights[i - 1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])

    return dp[n][capacity]

def coin_change(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1  # 初始化，金额为 0 的组合数为 1

    for coin in coins:
        for j in range(coin, amount + 1):
            dp[j] += dp[j - coin]

    return dp[amount]

import sys

def tsp(n, dist):
    # 数量为2^n的二维数组
    INF = sys.maxsize
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # 从城市0出发

    for mask in range(1 << n):
        for i in range(n):
            # 如果状态mask中包含城市i
            if mask & (1 << i):
                # 尝试从其他城市j转移到i
                for j in range(n):
                    if mask & (1 << j) and j != i:
                        dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + dist[j][i])

    all_visited = (1 << n) - 1  # 所有城市都已访问
    ans = min(dp[all_visited][i] + dist[i][0] for i in range(1, n))
    
    return ans

# 示例输入
cities = 4
distances = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

result = tsp(cities, distances)
print("最小旅行成本:", result)

def coin_change(coins, amount):
    coins.sort(reverse=True)  # 从大到小排序
    count = 0
    for coin in coins:
        while amount >= coin:  # 使用尽可能多的当前面额
            amount -= coin
            count += 1
    return count

coins = [1, 5, 10, 25]
amount = 30
print(coin_change(coins, amount))  # 输出: 2

def interval_scheduling(activities):
    # 按照结束时间排序
    activities.sort(key=lambda x: x[1])
    last_end_time = 0
    count = 0
    for activity in activities:
        start, end = activity
        if start >= last_end_time:  # 如果当前活动可以被选择
            count += 1
            last_end_time = end  # 更新最后结束时间
    return count

activities = [(1, 3), (2, 5), (4, 6), (5, 8)]
print(interval_scheduling(activities))  # 输出: 3

def activity_selection(activities):
    # 排序
    activities.sort(key=lambda x: x[1])
    
    selected_activities = []
    last_end_time = 0
    
    for start, end in activities:
        if start >= last_end_time:
            selected_activities.append((start, end))
            last_end_time = end
    
    return selected_activities

activities = [(1, 3), (2, 5), (4, 6), (6, 7), (5, 8)]
print(activity_selection(activities))

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][W]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
W = 5
print(knapsack(weights, values, W))

def coin_change(coins, amount):
    coins.sort(reverse=True)  # 从大到小排序
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count if amount == 0 else -1

coins = [4, 3, 1]
amount = 6
print(coin_change(coins, amount))  # 输出: 3

def activity_selection(activities):
    activities.sort(key=lambda x: x[1])  # 按结束时间排序
    selected = [activities[0]]  # 选择第一个活动
    last_end_time = activities[0][1]
    
    for i in range(1, len(activities)):
        if activities[i][0] >= last_end_time:  # 不重叠
            selected.append(activities[i])
            last_end_time = activities[i][1]
    
    return selected

activities = [(1, 3), (2, 5), (4, 6), (5, 7), (3, 4)]
print(activity_selection(activities))  # 输出: [(1, 3), (4, 6), (5, 7)]

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
    
    def find(self, p):
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p])
        return self.parent[p]
    
    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)
        if rootP != rootQ:
            self.parent[rootP] = rootQ

def kruskal(num_vertices, edges):
    edges.sort(key=lambda x: x[2])  # 按权重排序
    uf = UnionFind(num_vertices)
    mst = []
    
    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):  # 不形成回路
            uf.union(u, v)
            mst.append((u, v, weight))
    
    return mst

edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
print(kruskal(4, edges))