最小交换

---

时间限制：4 sec

空间限制：256 MB

问题描述

给定一个 1 到 n 的排列（即一个序列，其中 [1,n] 之间的正整数每个都出现了恰好 1 次）。

你可以花 1 元钱交换两个相邻的数。

现在，你希望把它们升序排序。求你完成这个目标最少需要花费多少元钱。

输入格式

第一行一个整数 n，表示排列长度。

接下来一行 n 个用空格隔开的正整数，描述这个排列。

输出格式

输出一行一个非负整数，表示完成目标最少需要花多少元钱。

样例输入

3
3 2 1

样例输出

3

样例解释

你可以：

花 1 元交换 1,2，序列变成 3 1 2。

花 1 元交换 1,3，序列变成 1 3 2。

花 1 元交换 2,3，序列变成 1 2 3。

总共需要花 3 元。

可以证明不存在更优的解。

数据范围

对于 20% 的数据，保证 n<=7。

对于 60% 的数据，保证 n<=1,000。

对于 100% 的数据，保证 n<=200,000。

提示

[每次交换相邻的两个数都会使逆序对 +1 或 -1。]

[逆序对数目不为零时，一定存在相邻的逆序对。]

[因此最优策略显然是每次都让逆序对数目 -1。]

[所以答案即为逆序对数目。]

[朴素的算法时间复杂度是 O(n^2) 的。]

[用归并排序求逆序对数可以通过本题。需要提醒的是，答案可能超过 32 位整数的范围哦。]

[逆序对数目同样可以用树状数组优化朴素的 O(n^2) 算法，并获得和归并排序相同的时间复杂度。有兴趣的同学可以自行学习。]

代码实现 

def merge_and_count(arr, left, mid, right):
    i, j, k = left, mid + 1, 0
    count = 0
    temp = [0] * (right - left + 1)
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp[k] = arr[i]
            i += 1
        else:
            temp[k] = arr[j]
            count += mid - i + 1  # 计算逆序对数量
            j += 1
        k += 1
    while i <= mid:
        temp[k] = arr[i]
        i += 1
        k += 1
    while j <= right:
        temp[k] = arr[j]
        j += 1
        k += 1
    for i in range(len(temp)):
        arr[left + i] = temp[i]
    return count
def merge_sort_and_count(arr, left, right):
    count = 0
    if left < right:
        mid = (left + right) // 2
        count += 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 count
def 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)

楼尔邦德

---

时间限制：2 sec

空间限制：256 MB

问题描述

给定包含 n 个数的序列 A。

再给出 Q 个询问，每个询问包含一个数 x，询问的是序列 A 中不小于 x 的最小整数是多少（无解输出-1）。

输入格式

第一行一个数 n，表示序列长度。

第二行 n 个用空格隔开的正整数，描述序列中的每一个元素。保证这些元素都不会超过 10^9。

第三行一个正整数 Q，表示询问个数。

接下来 Q 行，每行一个正整数 x，描述一个询问。

输出格式

输出 Q 行依次回答 Q 个询问，每行一个正整数，表示对应询问的答案。

样例输入

3
3 2 5
6
1
2
3
4
5
6

样例输出

2
2
3
5
5
-1

数据范围

对于 50% 的数据，保证 n<=2000。

对于 100% 的数据，保证 n<=300,000。

提示

[如果我们先将原序列排序，那么我们就可以在它上面进行二分查找啦！]

[STL库中有二分查找的函数__std::lower_bound__，你可以学习一下它的使用。当然啦，作为初学者，还是建议自己实现二分查找哦！]

 代码实现

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    result = -1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] >= target:
            result = arr[mid]
            high = mid - 1
        else:
            low = mid + 1
    return result
def 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()

最短路

---

时间限制：4 sec

空间限制：256 MB

问题描述

给定一张 n 个点的无向带权图，节点的编号从 1 至 n，求从 S 到 T 的最短路径长度。

输入格式

第一行 4 个数 n,m,S, T，分别表示点数、边数、起点、终点。

接下来 m 行，每行 3 个正整数 u,v,w，描述一条 u 到 v 的双向边，边权为 w。

保证 1<=u,v<=n。

输出格式

输出一行一个整数，表示 S 到 T 的最短路。

样例输入

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

样例文件下载（包含第二个样例）

数据范围

本题共设置 12 个测试点。

对于前 10 个测试点，保证 n<=2500，m<=6200，对于每条边有 w<=1000。这部分数据有梯度。

对于所有的 12 个测试点，保证 n<=100,000，m<=250,000。

提示

[本题是 Dijkstra 算法的模板练习题。]

[使用朴素的 Dijkstra 算法可以通过前 10 个测试点。]

[使用堆或__std::priority_queue__优化的 Dijkstra 算法可以通过所有测试点。]

代码实现 

import heapq
def dijkstra(graph, start, end):
    n = len(graph)
    dist = [float('inf')] * n
    dist[start - 1] = 0
    pq = [(0, start)]
    while pq:
        curr_dist, node = heapq.heappop(pq)
        if curr_dist > dist[node - 1]:
            continue
        for neighbor, weight in graph[node]:
            new_dist = curr_dist + weight
            if new_dist < dist[neighbor - 1]:
                dist[neighbor - 1] = new_dist
                heapq.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)