网站开发可以申请著作权吗,wordpress自定义文章,中山做网络推广的公司,今天建设银行网站无法登录最小交换 时间限制#xff1a;4 sec 空间限制#xff1a;256 MB 问题描述 给定一个 1 到 n 的排列#xff08;即一个序列#xff0c;其中 [1,n] 之间的正整数每个都出现了恰好 1 次#xff09;。 你可以花 1 元钱交换两个相邻的数。 现在#xff0c;你希望把它们升序排序… 最小交换 时间限制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% 的数据保证 n7。 对于 60% 的数据保证 n1,000。 对于 100% 的数据保证 n200,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, 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) 楼尔邦德 时间限制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% 的数据保证 n2000。 对于 100% 的数据保证 n300,000。 提示 [如果我们先将原序列排序那么我们就可以在它上面进行二分查找啦] [STL库中有二分查找的函数__std::lower_bound__你可以学习一下它的使用。当然啦作为初学者还是建议自己实现二分查找哦] 代码实现 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()最短路 时间限制4 sec 空间限制256 MB 问题描述 给定一张 n 个点的无向带权图节点的编号从 1 至 n求从 S 到 T 的最短路径长度。 输入格式 第一行 4 个数 n,m,S, T分别表示点数、边数、起点、终点。 接下来 m 行每行 3 个正整数 u,v,w描述一条 u 到 v 的双向边边权为 w。 保证 1u,vn。 输出格式 输出一行一个整数表示 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 个测试点保证 n2500m6200对于每条边有 w1000。这部分数据有梯度。 对于所有的 12 个测试点保证 n100,000m250,000。 提示 [本题是 Dijkstra 算法的模板练习题。] [使用朴素的 Dijkstra 算法可以通过前 10 个测试点。] [使用堆或__std::priority_queue__优化的 Dijkstra 算法可以通过所有测试点。] 代码实现 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)
