CF1710E Two Arrays

本文主要是介绍CF1710E Two Arrays，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

*2400？*24000！

题意

用两个数组 \(a_1,a_2,\ldots,a_n\)、\(b_1,b_2,\ldots,b_m\) 描述一个 \(n\times m\) 的网格图，\((i,j)\) 的权值为 \(a_i+b_j\)。

一开始有个车位于 \((1,1)\)，Alice 和 Bob 轮流操作，一次操作可以选择：

1. 横向移动车至与其同一行的任意一个格子；
2. 纵向移动车至与其同一列的任意一个格子；
3. 结束游戏。

特别地，不能将车移动至一个已经被踩过 \(1000\) 次的格子，最后局面的权值即为车所在格子的权值。

Alice 想最大化，Bob 想最小化，两人均最优策略，问最后的权值。

\(n,m\leq 2\times 10^5\), \(a_i,b_i \leq 5\times 10^8\)。

题解

首先二分答案 \(x\)，那么 Alice 一旦遇到比 \(x\) 大的局面就会立刻结束，Bob 同理。那么我们把格子按照权值，\(\ge x\) 的为白色，\(\leq x\) 的为黑色，也就是说，Alice 只能走白格，Bob 只能走黑格，谁走不动谁输。

这篇关于CF1710E Two Arrays的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！