我正在玩下面的问题,并采取蛮力的方法,但无法提出一个很好的解决方案.问题如下:
有2*N张牌.你和你的对手将它们分开(N卡给你,N给他们).你确切地知道他们拥有什么牌以及他们将以何种顺序进行比赛.
游戏规则如下:对于前N/2轮,具有最高卡的人获胜并且在最后N/2轮中,具有最低卡的人获胜.
鉴于这些规则和你的对手在那里打牌的顺序,你可以获得的最大胜利数量是多少.
例:
你有牌:2,5,6,7.你的对手有牌:1,8,4,3并按顺序播放.
你可以得到的最高得分是2,因为你打7到1,输掉第2轮和第3轮,然后在最后一轮打2赢.
我的想法:将你的牌分成两堆,你的号码较大,编号较小.然后找出最佳匹配.
伪代码/算法的想法将不胜感激.
编辑:共有N轮.前N/2轮:较高的牌获胜.最后N/2轮:较低的牌获胜.N必须是均匀的.
所以我提出了一个有趣的问题,看看是否有一种有效的解决方法.所以基本上有一个平衡的二叉树,其中保存了id号(它不是bst所以没有正式的安排).您有大量的查询来查找有多少节点.保证对于每个节点E,左子树将具有与该节点E上的右子树一样多或多一个节点.请求程序找出有多少节点的最佳方式是什么？例如给出这样的树:
1
4 2
3
该程序将提供以下输出:
Query: 1
Response: 4 2
Query: 4
Response 3
Query: 3
Response: 0 0
Query: 2
Response: 0 0
Answer: 4