冰火战士

题意分析 对于每次修改后的情况,求一个最大的 $k$ ,使得温度不大于 $k$ 的冰系战士的能量和与温度不小于 $k$ 的火系战士的能量和的最小值最大。 思路分析 显然所求的 $k$ 一定是某战士的温度,因此先将数据进行升序排序离散化处理。此时问题就转变为,设冰系与火系战士组成的序列分别为 $a,b$ ,则求一个最大的 $x$ ,使得在 $x$ 位置 $a$ 的前缀和与 $b$...

题目 点这里看题目。 分析 设\(F(T)\)为温度为\(T\)的时候火系战士能量和,\(I(T)\)为\(T\)时冰系战士能量和。 显然我们需要求: \[\max\{\min\{F(T),I(T)\}\}\] 另一个显然的事情是,\(F(T)\)是一个后缀和,\(I(T)\)是一个前缀和;因而\(F(T)\)单减,\(I(T)\)单增。 那么\(\min\{F(T)...

知识点: 原题面 Loj Luogu 扯 考场上写了二分 + 树状数组。没想到可以再二分一次于是加了个 set,水了 60。 当时还不知道线段树上二分这种傻逼玩意= =今日学到虚脱。 题意简述 简不动,简不动。 分析题意 读完题发现全是废话。可总结出下面几个结论: 将冰火人按温度升序排序,冰人选择的是一段前缀,火人选择的是一段后缀。答案即 选择的冰人能量总和 和 火人能量总和 较小的的一方的两倍...