AcWing 4965. 三国游戏
原题链接
简单
作者:
ZYPTD
,
2024-03-28 22:08:41
,
所有人可见
,
阅读 8
贪心(python版本)
本质上还是暴力枚举,不过时间复杂度为 $O(n)$
python 代码,相关注意事项均注释在代码中
def compare(a,b,c,n):
cnt,s=0,0
tmp=[0]*n#这里不能直接乘以1e9,不然一排序,列表最前面的就是一堆0了
for i in range(n):
tmp[i]=a[i]-(b[i]+c[i])#用类似C++的赋值来初始化tmp
#转换成一个和值大于0的题目,这样就将三元函数一元化,降低空间复杂度。
tmp.sort()#直接排序即可
for i in range(n-1,-1,-1):#为了贪心,保证和大于0,所以就是要尽可能找大的。由于没有其它额外的约束条件,因此直接贪心而不是动态规划
if s+tmp[i]>0:
s+=tmp[i]
cnt+=1
else:#如果小于0,即不满足条件,就直接停了,最终cnt即为结果
break
return cnt
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=0
ans=max(ans,compare(a,b,c,n))
ans=max(ans,compare(b,a,c,n))
ans=max(ans,compare(c,b,a,n))
if ans==0:
print(-1)
else:
print(ans)