用Python解决zoj1944
时间: 2023-06-17 13:07:53 浏览: 58
ZOJ1944是一个经典的贪心算法问题,需要用Python编写代码实现。下面是我的代码实现,希望对你有所帮助:
```python
while True:
n, m = map(int, input().split())
if n == 0 and m == 0:
break
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
ans = 0
j = 0
for i in range(n):
while j < m - 1 and b[j] < a[i]:
j += 1
if b[j] >= a[i]:
ans += b[j]
j += 1
if j == m:
print(ans)
else:
print("Loowater is doomed!")
```
这个代码的实现思路是先对两个列表进行排序,然后从小到大遍历每一个龙的大小,同时在每一次遍历中,从小到大遍历每一个骑士的能力值,找到能力值大于等于当前龙的骑士,并选择能力值最小的骑士进行匹配。如果所有骑士都无法匹配当前龙,那么就无法完成任务,输出"Loowater is doomed!",否则输出所有匹配骑士的能力值之和。
相关问题
用python写zoj1944的答案代码
ZOJ1944题目描述:
给定一个N*M的矩阵,每个元素是一个非负整数。现在走迷宫,从左上角走到右下角,只能向右或者向下走,求路径上的元素和最小是多少。
输入格式:
第一行是一个正整数T,表示有T组测试数据。
每组数据第一行是两个正整数N和M(1<=N,M<=100),表示矩阵的行数和列数。
接下来是一个N*M的矩阵,每个元素是一个非负整数,表示从左上角走到这个点需要的代价。
输出格式:
对于每组测试数据,输出一行,表示从左上角走到右下角的最小代价。
样例输入:
2
3 3
1 3 1
1 5 1
4 2 1
2 2
1 2
3 4
样例输出:
7
3
答案代码如下:
用python做zoj2212
ZOJ2212 题目描述:
有一个由若干行若干列的矩阵,每个位置上有一个数字,现在要把这个矩阵分成若干个区域,每个区域内部的数字相同,且相邻的区域不能有相同的数字。请你求出最多能将这个矩阵分成多少个区域。
输入:
输入的第一行有两个整数,分别表示矩阵的行数和列数。接下来的若干行中,每行有若干个整数,表示矩阵中的数字。
输出:
输出一个整数,表示最多能将这个矩阵分成多少个区域。
样例输入:
3 3
1 2 3
1 4 5
6 7 8
样例输出:
5
解题思路:
本题可以用深度优先搜索(DFS)或广度优先搜索(BFS)来实现。以 DFS 为例,对每个区域建立一个 visited 数组,表示该区域中的元素是否已被访问过。对于每个未访问过的区域,从该区域中任选一个元素开始进行 DFS,将该区域中的所有元素标记为已访问,并将这个区域中的元素值记为当前搜索的值。继续搜索,直到找不到相邻区域中有相同元素值的区域为止。这样就完成了一个区域的搜索。接着,继续搜索下一个未访问过的区域,直到所有区域都被访问过为止。
代码实现: