一艘飞船正在太阳系执行任务,途中遭遇太阳风暴。飞船呈长条状,有n个节点分别装着价值为v同的设
备。节点之间有n-1个连接道路,道路长d,且该道路不受太阳风暴影响。
有一种护盾,能够保护半径为k的范围不受风暴影响,且飞船上载有s个该护盾。
现求安放多少个护盾(<=s),分别在哪些节点上,才能保护价值最多的设备,且保证节点之间是连接的(节点之间道路不必完全在护盾范围里,但两个节点之间的节点如果被破坏,就不算作连接的节点,即不能只保护断开的,价值高的节点)。
输入格式:
第一行3个整数,表示n个节点,S个护盾,护盾半径为k。
第二行n-1个整数,第i个整数表示第;个节点到第i+1个节点的距离。
第三行n个整数,表示节点的价值。
输出格式:
第一行1个整数x,表示安放几个盾牌。
第二行×个整数,表示盾牌安放在第几个节点。
以下是我的代码
n, s, k = map(int, input().split())
a = [0] * (n + 1)
a = [0] * (n + 1)
a[1] = 0
a[2:] = map(int, input().split())
for i in range(2, n + 1):
a[i] += a[i - 1]
b= list(map(int, input().split()))
mx, l, num = 0, 0, 0
for i in range(1, n + 1):
flag, flag_s, temp_mx = a[i] - 1, s, 0
for t in range(i, n + 1):
if flag < a[t]:
if flag_s == 0:
break
far = 0
for j in range(t, n + 1):
if a[j] - k <= a[t]:
far = j
else:
break
flag = a[far] + k
flag_s -= 1
temp_mx += b[t - 1]
if temp_mx > mx:
mx = temp_mx
l = i
flag, flag_s = a[l] - 1,s
ans = []
for t in range(l, n + 1):
if flag < a[t]:
if flag_s == 0:
break
far = 0
for j in range(t, n + 1):
if a[j] - k <= a[t]:
far = j
else:
break
flag = a[far] + k
flag_s -= 1
ans.append(far)
num += 1
print(num)
print(*ans)
这个可以用Python运行但是判分的时候只对了一半,请问是哪里出了问题?
根据题目描述,需要保证节点之间是连接的,但是你的代码中没有考虑到这一点。在选择安放护盾的时候,需要保证当前选择的节点到下一个选择的节点之间的所有节点都在护盾的保护范围内,否则就不满足节点之间是连接的条件。
修改方法:在第二个循环中,需要增加一个变量 last
,表示上一个选择的节点,然后在选择下一个节点时,需要判断当前节点到上一个节点之间的所有节点是否都在护盾的保护范围内。如果不在,则需要选择一个更靠前的节点,直到满足条件为止。具体实现可以参考下面的代码:
n, s, k = map(int, input().split())
a = [0] * (n + 1)
a[1] = 0
a[2:] = map(int, input().split())
for i in range(2, n + 1):
a[i] += a[i - 1]
b = list(map(int, input().split()))
mx, l, num = 0, 0, 0
for i in range(1, n + 1):
flag, flag_s, temp_mx = a[i] - 1, s, 0
for t in range(i, n + 1):
if flag < a[t]:
if flag_s == 0:
break
far = 0
for j in range(t, n + 1):
if a[j] - k <= a[t]:
far = j
else:
break
flag = a[far] + k
flag_s -= 1
temp_mx += b[t - 1]
if temp_mx > mx:
mx = temp_mx
l = i
flag, flag_s = a[l] - 1, s
ans = []
last = l - 1
for t in range(l, n + 1):
if flag < a[t]:
if flag_s == 0:
break
far = 0
for j in range(t, n + 1):
if a[j] - k <= a[t]:
if a[j] > a[last] + k:
far = j
else:
continue
else:
break
if far == 0:
break
flag = a[far] + k
flag_s -= 1
ans.append(far)
last = far
num += 1
print(num)
print(*ans)
注意:在选择下一个节点时,需要判断当前节点到上一个节点之间的所有节点是否都在护盾的保护范围内,如果不在,则需要选择一个更靠前的节点,直到满足条件为止。