@SomeBottle 在 Leetcode每日一题 —— 1927. 求和游戏 中发帖
Alice 和 Bob 这一对苦命鸳鸯又来了!
思路
如果采取最优策略的话,Alice 的目的是让两半尽量不相等,而 Bob 则是让两半尽量相等。
题目最终结果因此就取决于替换了问号后能不能使得左右各自数字和的差为 0。
分类讨论:
如果问号数量总和为奇数,那么 Alice 必然能多放一次来打破平衡,是必赢的。
如果问号数量总和为偶数,必然是 Alice 和 Bob 各放一半:
若左右两部分问号数量相等,Alice 和 Bob 各放一半,Bob 怎么样也能抵消 Alice 的改动,这种情况相当于问号不存在了,只用看左右其他数字的和的差是不是 0;
若左右两部分问号数量不相等,因为问号数量总和是偶数,左右问号数量差必然也是偶数。也就是说必然是一边比另一边多出偶数个问号,对于相同的部分我们按 2.1 处理,多出的部分依旧是 Alice 和 Bob 各能操作一半:
A...