标签: 二分

「CodeForces 1288D」 Minimax Problem

You are given 𝑛 arrays 𝑎1, 𝑎2, ..., 𝑎𝑛; each array consists of exactly 𝑚 integers. We denote the 𝑦-th element of the 𝑥-th array as 𝑎𝑥,𝑦.

You have to choose two arrays 𝑎𝑖 and 𝑎𝑗 (1≤𝑖,𝑗≤𝑛, it is possible that 𝑖=𝑗). After that, you will obtain a new array 𝑏 consisting of 𝑚 integers, such that for every k[1,m]k \in [1, m] bk=max(ai,k,aj,k)b_k = \max(a_{i, k}, a_{j, k}) .

Your goal is to choose 𝑖𝑖 and 𝑗𝑗 so that the value of minmink=1mbk\min \limits_{k = 1}^{m} b_k is maximum possible.

「NOIP2015」运输计划

公元2044 年,人类进入了宇宙纪元。

L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司, 该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从 uiu_i 号星球沿最快的宇航路径飞行到 viv_i 号星球去。显然,飞船驶过一条航道是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tjt_j,并且任意两艘飞船之间不会产生任何干扰。

「BZOJ2144」 跳跳棋

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的
游戏:棋盘上有3颗棋子,分别在a,b,c这三个位置。我们要通过最少的跳动把他们的位置移动成x,y,z。(棋
子是没有区别的)跳动的规则很简单,任意选一颗棋子,对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只
允许跳过1颗棋子。