蓝桥杯思维训练营（四）

小红打怪

小红打怪

思路分析：可以看到ai的范围较大，如果我们直接一个个进行暴力遍历的话，会超时。当我们的攻击的次数越大的时候，怪物的血量就会越少，这里就有一个单调的规律在里面，我们可以考虑以 攻击的轮次作为二分的变量，进行二分，对于每一个二分的mid,我们设计好对应的check函数，判断在mid轮攻击下，是否可以消灭所有的怪兽

n = int(input())
num = list(map(int,input().split()))
n = len(num)def check(mid):# 判断在mid次数之内是否将怪物全部消灭# 先处理群体攻击newnum = [max(0,u-mid) for u in num ]# 再处理相邻的攻击，遇到相邻才处理，多余的次数转变为单次攻击count = midfor i in range(n-1):if newnum[i]!=0 and count!=0:# 这个sub的值别漏了对count的判断sub = min(newnum[i],newnum[i+1],count)newnum[i]-=subnewnum[i+1]-=subcount-=subif count==0:break# 处理单次操作，如果count还有剩余，那么总的操作次数是 mid+counta = sum(newnum)if a <= mid + count:return Trueelse:return False# 二分操作
left,right = 0,max(num)
while left<=right:mid = (left+right)//2if check(mid):right=mid-1else:left=mid+1
print(left)

算法实现的细节：首先check函数首先处理的是全局攻击，然后再进行处理相邻的攻击(相邻攻击的时候，为了节省次数，我们只处理相邻的情况，每次减去的部分sub是min(newnum[i],newnum[i+1],count))，如果减完之后，count有剩余，则加到单个攻击里面，最后判断sum剩余的情况与我们的攻击次数是否够

    count = midfor i in range(n-1):if newnum[i]!=0 and count!=0:# 这个sub的值别漏了对count的判断sub = min(newnum[i],newnum[i+1],count)newnum[i]-=subnewnum[i+1]-=subcount-=subif count==0:break

494.目标和

494.目标和

思路分析：我们可以使用类似于0-1背包的问题，选择加的整数，
要加的整数为p ,整个数组的和为s,那么要减去的数目就是s-p ,也就是有 p - (s-p) = target,经过转换就有 p = (s+target)/2,也就是 这个 target + s必须是偶数,由于nums[i]没有负数，所以target<0的时候也无解

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:target += sum(nums)if target < 0 or target % 2 :return 0target //= 2n = len(nums)@cache# dfs(i,c)表示，前i中数字中，满足target的组合数def dfs(i,c):# i < 0，表示选择完了if i < 0:return 1 if c == 0 else 0if c < nums[i]:return dfs(i-1,c)return dfs(i-1,c) + dfs(i-1,c-nums[i])return dfs(n-1,target)