Codeforces #679 div2 简要题解

发现 $n$ 为偶数，两两配对取相反数即可

通过输入输出，我们可以知道 $n$ 行 $m$ 列的大小关系。

可以找到每个元素在原表中对应的行和列，利用 $(i-1)*m+j$ 映射就好。

发现一个 $a$ 可以对应多个 $b$ ，我们考虑把每个 $b-a$ 排序。

问题即为求这个数列中每个 $b$ 选一个元素的最小极差。

要保证每个 $b$ 都出现，我们可以考虑双指针，并记录一下未出现元素的个数 $cnt$ 。

当 $cnt=0$ 时，就一直指针左移并统计答案。

~~第一次fst/kk~~

考虑维护一个栈，栈内加入的是下标，并未赋值。

把购买操作看成弹栈，并把栈顶代表的下标赋成当前的 $x$ 。

每次弹栈时，维护一个标记，表示当前栈内元素曾经的最小值。

由于只会在弹栈中考虑判定大小，所以加在栈顶就好了。

不合法有两种情况：

之后模拟就好了，复杂度 $O(n)$ ，也不需要离线和倒推。

更新标记时一定要和原本的标记取max！！！

结论题。

首先无限的情况很好判定，只要 $a>b*c$ 就行。

考虑最大的伤害一定是在某一次攻击后的瞬间，所以我们只要找到最后一次攻击是第几次即可。

不难发现，在 $\frac {a-1}{b}$ 秒前，我们这次伤害都能打掉敌人血，而这之后则不然。

我们要在这段时间内尽可能创造出最大伤害，否则相当于没打。

这之间我们最多能打 $\lfloor\frac{a-1}{bd}\rfloor$ 次，造成的伤害 $\lfloor\frac{a-1}{bd}\rfloor\times a$ 。

最后答案扣除敌人恢的血就好了，这一段时间内敌人一直在回血。

（这里再看看 cf 的题解）