社区讨论

关于第一篇题解中的证明

P2868[USACO07DEC] Sightseeing Cows G参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@locvouzs
此快照首次捕获于
2023/10/30 20:30
2 年前
此快照最后确认于
2023/11/05 07:01
2 年前
查看原帖
我的题解,我伪证了,我补过/kel
由于这题关闭题解提交通道了,因此只能在讨论区里补充,不用重新走一遍特许流程了。
正确证明如下:
目标仍旧是证明 F1T1F1+F2FxT1+T2\dfrac{F_1}{T_1}\geq\dfrac{F_1+F_2-F_x}{T_1+T_2}F2T2F1+F2FxT1+T2\dfrac{F_2}{T_2}\geq \dfrac{F_1+F_2-F_x}{T_1+T_2}
或很难处理,可以考虑反证将或转化为和。那么问题就变成了证明下两式不可能同时成立:
T1F1+T2F1<T1F1+T1F2T1FxT1F2+T2F2<T2F1+T2F2T2FxT_1F_1+T_2F_1< T_1F_1+T_1F_2-T_1F_x\\ T_1F_2+T_2F_2< T_2F_1+T_2F_2-T_2F_x
两式相加,约掉 (T1+T2)(F1+F2)(T_1+T_2)(F_1+F_2) 即可。
这个证明成立的条件是 T1+T20T_1+T_2\neq0Fx(T1+T2)0F_x(T_1+T_2)\leq0,容易验证题目满足这一条件。

回复

2 条回复,欢迎继续交流。

正在加载回复...