USACO analysis
yff |
17 Nov 2020
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
题目
给 $N$ 头奶牛按以下规则排序：
- 有些奶牛要按给定顺序排序
- 有些奶牛只能排在某个位置
- 满足前两个规则的前提下，奶牛 1 要尽量往前排。
求出奶牛 1 在队伍中出现的最早位置
思路
按题目给的规则排序
复杂度分析
$O(n^2)$
代码
lines = open('milkorder.in').read().strip().split('\n')
n, m, k = list(map(int, lines[0].split(' ')))
order = list(map(int, lines[1].split(' ')))
pos_cow = {}
for i in range(2, k + 2):
line = list(map(int, lines[i].split(' ')))
pos_cow[line[0]] = line[1]
pos = [0] * (n + 1)
for i in pos_cow:
pos[pos_cow[i]] = i
if 1 in order:
cur = 1
for num in range(0, len(order)):
if order[num] in pos:
cur = pos.index(order[num]) + 1
else:
for i in range(cur, len(pos)):
if pos[i] == 0:
pos[i] = order[num]
cur = i + 1
break
else:
cur = len(pos) - 1
for num in range(len(order) - 1, -1, -1):
if order[num] in pos:
cur = pos.index(order[num]) - 1
else:
for i in range(cur, 0, -1):
if pos[i] == 0:
pos[i] = order[num]
cur = i - 1
break
file = open('milkorder.out', 'w')
if 1 in pos:
file.write(str(pos.index(1)))
print(pos.index(1))
else:
for i in range(1, len(pos)):
if pos[i] == 0:
print(i)
file.write(str(i))
break
file.close()
