这里的问题是找到所有整数点的集合,它给出了来自给定点集的所有曼哈顿距离的最小总和!
例如:
让我们有一组给定的点{P1,P2,P3 ... Pn}
基本问题是找到一个点X,它将在点{P1,P2,P3 ... Pn}的所有距离上具有最小总和.
即| P1-X | + | P2-X | + .... + | Pn-X | = D,其中D将在所有X上最小.
更进一步,可以有多于一个满足上述条件的X值.也就是说,可能有多个X可以给出相同的值D.所以,我们需要找到所有这样的X.
任何人都可以想到的一个基本方法是找到输入的中位数,然后对这篇文章中提到的坐标进行暴力破解.
但是这种方法的问题是:如果中位数给出两个非常分开的值,那么我们最终会强制所有在给定时间内永远不会运行的点.
那么,是否存在任何其他方法即使在点相距很远时也会给出结果(中位数给出的范围大约为10 ^ 9).
Alice和Bob玩下面的游戏:
1)他们选择开头的前N个数字的排列.
2)他们交替上场,爱丽丝先上场.
3)在一个回合中,他们可以从排列中删除任何一个剩余的数字.
4)当剩余数字形成递增序列时,游戏结束.最后一个回合(在序列变得增加之后)的人赢得比赛.
假设两者都发挥得最好,谁赢了比赛？
输入:第一行包含测试用例数T.T测试用例如下.每个案例在第一行包含一个整数N,然后在第二行包含整数1..N的排列.
输出:输出T行,每个测试用例一行,如果Alice赢了游戏则包含"Alice",否则包含"Bob".
样本输入:
2
3
1 3 2
五
5 3 2 1 4
样本输出:
爱丽丝
短发
约束:
1 <= T <= 100
2 <= N <= 15
排列最初不会是增加的顺序.
我想解决上面的问题.我已经衍生到很远,但我陷入了困境.请帮我继续.
在上述问题中,对于长度为2的排列,玩家1总是获胜.
对于长度为3的置换,如果字符串严格增加或减少,则播放器2获胜.
对于长度为4的排列,如果玩家1能够通过移除角色使弦完全增加或减少,则她赢得其他玩家2胜.
因此得出的结论是:
如果当前玩家能够使字符串严格增加他/她获胜.(琐碎案例)
如果他/她能够使其严格减少,则获胜者由该序列中的元素数量决定.如果该序列中有偶数个元素,则当前玩家会失败,否则获胜.
但是,如果结果字符串既不增加也不减少,应该怎么办？