[已解决]Python：每日一题 352

zltzlt

永恒的蓝色梦想 发表于 2020-3-16 11:35
昨天的题太难了，今天要不出点简单的把

永恒的蓝色梦想

zltzlt 发表于 2020-3-16 11:40

动态规划，到现在都没搞懂

fan1993423

我就想问3楼和塔利班的答案都是自己想出来的吗？感觉思路非常规

zltzlt

蒋博文 发表于 2020-3-15 17:55

是你自己想的吗？

塔利班

fan1993423 发表于 2020-3-16 11:50
我就想问3楼和塔利班的答案都是自己想出来的吗？感觉思路非常规

是自己想的，但是自己运行发现太慢了，而且数组长了还有递归限制，动态规划就是搞状态转移方程的，而且感觉不适思路很麻烦，就是比较左边取和右边取而已

fan1993423

刚也发现了，偶数个数的情况。都是先手胜或和平局，所以代码可以优化一下偶数的情况，，当然这次不严谨，有些平局我就默认先手胜

1. A_player,B_player=0,0
   
2. def fun352(lst):
   
3.     if not len(lst):return '平局'
   
4.     elif len(lst)==1 and lst[0]>0:return True
   
5.     elif len(lst)==1 and lst[0]==0:return '平局'
   
6.     elif not len(lst)%2:
   
7.         if len(set(lst))==1:return '平局'
   
8.         else:return True
   
9.     else:
   
10.         def recursive(lst,player,i):
    
11.             global A_player,B_player
    
12.             if len(lst)==1 and i%2:
    
13.                 B_player+=lst[0]
    
14.                 return
    
15.             elif len(lst)==1 and not i%2:
    
16.                 A_player+=lst[0]
    
17.                 return
    
18.             if lst[0]>=lst[1] and lst[-1]>=lst[-2]:
    
19.                 if lst[0]>=lst[-1]:
    
20.                     player+=lst[0]
    
21.                     lst.pop(0)
    
22.                 else:
    
23.                     player+=lst[-1]
    
24.                     lst.pop(-1)
    
25.             elif lst[0]>=lst[1] and lst[-1]<lst[-2]:
    
26.                 player+=lst[0]
    
27.                 lst.pop(0)
    
28.             elif lst[0]<lst[1] and lst[-1]>=lst[-2]:
    
29.                 player+=lst[-1]
    
30.                 lst.pop(-1)
    
31.             else:
    
32.                 if (lst[1]-lst[0])>=(lst[-2]-lst[-1]):
    
33.                     player+=lst[-1]
    
34.                     lst.pop(-1)
    
35.                 else:
    
36.                     player+=lst[0]
    
37.                     lst.pop(0)
    
38.             i+=1
    
39.             if i%2:
    
40.                 A_player+=player
    
41.                 recursive(lst,0,i)
    
42.             else:
    
43.                 B_player+=player
    
44.                 recursive(lst,0,i)
    
45.         recursive(lst,0,0)
    
46.     return True if A_player>B_player else '平局' if A_player==B_player else False

复制代码

fan1993423

塔利班 发表于 2020-3-16 11:58
是自己想的，但是自己运行发现太慢了，而且数组长了还有递归限制，动态规划就是搞状态转移方程的，而且感 ...

好吧，我开始没先到二路递归那边去

zltzlt

TJBEST 发表于 2020-3-15 17:52
测试了一下，比较慢 先这样，我再想想有什么好办法。测试1000个数接近秒级 不甚理想。

解答错误

输入：[1, 2, 99]
输出：False
预期结果：True

玩家 1 可以先拿 99

zltzlt

蒋博文 发表于 2020-3-15 17:55

52 ms

zltzlt

ouyunfu 发表于 2020-3-15 18:50

解答错误

输入：[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
输出：False
预期结果：True

zltzlt

kinkon 发表于 2020-3-15 19:50
编出来的程序自己都看不懂，没有数据计算，单纯的选大小，除了快一点，其他的只能emmm了

解答错误

输入：[2, 2, 454, 2, 2]
输出：True
预期结果：False

zltzlt

546623863 发表于 2020-3-15 20:27
例子测试的没啥问题，估计效率不会太高

解答错误

输入：[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
输出：False
预期结果：True

zltzlt

平局返回 True

zltzlt

Unicorn# 发表于 2020-3-15 20:32

https://fishc.com.cn/forum.php?m ... 723&pid=4482239

zltzlt

fan1993423 发表于 2020-3-15 20:50
平局怎么办，还有0分的吗？

https://fishc.com.cn/forum.php?m ... 723&pid=4482239

zltzlt

fan1993423 发表于 2020-3-15 22:03

解答错误

输入：[1, 89, 3]
输出：True
预期结果：False

zltzlt

塔利班 发表于 2020-3-15 23:16
回头一看之前的通项是对了，但是递归限制太多，偶数个必定先手不输，输了就copyB走法

第二个有错，第一个 6184 ms

zltzlt

fan1993423 发表于 2020-3-16 12:04
刚也发现了，偶数个数的情况。都是先手胜或和平局，所以代码可以优化一下偶数的情况，，当然这次不严谨，有 ...

输入 [1, 1, 1] 结果有误

永恒的蓝色梦想

zltzlt 发表于 2020-3-16 13:33
第二个有错，第一个 6184 ms

我的天哪……是不是python不适合用递归

蒋博文

zltzlt 发表于 2020-3-16 11:53
是你自己想的吗？

是啊。
我做过类似的题