给定 n 个人,每个人有 m 个测量结果.取所有人所有测量结果的中位数(偶数时下去整)为最终结果.
已知测量结果应该是 goal,问至少修改几个测量结果可以使得结果恰好为 goal,在这种情况下最少需要参与修改的人数又是多少.
如果要让结果恰好为 goal,那么比 goal 小的数和比 goal 大的数都不能超过一半,显然这两边只会有一边不符合.
于是我们只要关心这一边需要修改几个数就好了,并且现在只需要考虑一边,第二问只要统计出每个人可以带来的贡献,排序贪心即可.
这样我们就发现了一个子问题!
那么实际的答案可能第一个数不为 1,所以开始再额外枚举一次约数就好.
复杂度虽然不太容易估计,但貌似不记忆化也能过.
- 如果恰好差小于等于 maxDiff,那么大的一方获胜,并得到 ifNear 分.
双方都采取最优策略时,问 Alice 报的数恰好为 query 的概率.
第一眼感觉这个题很神,看了一下大家后来都是高斯消元做的.但是不知道怎么列方程.后来请教了一下毕克老师,毕老师说其实这个问题跟剪刀石头布是一样的,就你想象一个剪刀石头布游戏,然后给你一个收益矩阵.
对方把自己的策略的概率分布向量已经告诉你了,在最优情况下,你发现你即便知道这个向量也并不能让你取得任何优势.
这就是传说中的 纳什均衡,于是只要设表示报 x_i 的概率,根据上面这些关系,列出线性方程组,高斯消元即可.
纳什均衡虽然提供了 n 组方程,但是 rank 似乎是 n-1 的,最后别忘了加上所有概率分布之和等于 1.
可以预计答案不会很大,可以带极限数据跑一下看看边界.