标签：geq log text 测量 差分 times P4926 1007 array

算法

约束条件 \(\to\) 差分约束

如果令所有选手都不能女装

对于 \(o = 1\) 的约束条件, 有 ( 其中 \(M_i\) 表示选手 \(i\) 的得分 )

\[M_A \geq (k - T) \times M_B \]

对于 \(o = 2\) 的约束条件, 有

\[M_B < (k + T) \times M_A \]

使得不等式组无解

这样的不等式, 在不是所有选手的分数确定的情况下, 怎样转化成差分约束呢?

先假设 \(T\) 一定,

完全可以将不等式转化成差分约束的条件, 具体的

\[\left\{ \begin{array}{lr} M_i > 0, i \in [1, n] \text{ }, & \\ M_{A_i} \geq (k_i - T) \times M_{B_i} \text{ } , o_i = 1, & \\ M_{B_i} < (k_i + T) \times M_{A_i} \text{ } , o_i = 2 & \\ \end{array} \right. \]

将其用 \(\log\) 运算变形

\[\Downarrow \]

\[\left\{ \begin{array}{lr} M_i > 0, i \in [1, n] \text{ }, & \\ \log(M_{A_i}) \geq \log(k_i - T) + \log(M_{B_i}) \text{ } , o_i = 1, & \\ \log(M_{B_i}) < \log(k_i + T) + \log(M_{A_i}) \text{ } , o_i = 2 & \\ \end{array} \right. \]

---

二分答案 \(T\) , 无解输出 \(-1\) 当且仅当 \(T = 0\) 时方程式依然有解

代码

略

总结

对于乘法运算, 取 \(\log\) 可以实现变 \(\times\) 为 \(+\)

先假设确定, 再二分此值可以解决特定的一类问题

标签：geq,log,text,测量,差分,times,P4926,1007,array
From： https://www.cnblogs.com/YzaCsp/p/18546346