社区讨论

本题排序规则证明

yylch
P11376[GESP202412 六级] 运送物资参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@mjnnb9i4
此快照首次捕获于
2025/12/27 09:52
2 个月前
此快照最后确认于
2025/12/28 21:00
2 个月前
查看原帖
排序不等式
假设对于两辆车i,ji,j，ii在p1p_1，jj在p2p_2，如果把ii移到jj更优，就要求原来的总代价大于交换后的总代价，即：
2aip1+2bi(x−p1)+2ajp2+2bj(x−p2)>2aip2+2bi(x−p2)+2ajp1+2bj(x−p1)2a_ip_1 + 2b_i(x - p_1) + 2a_jp_2 + 2b_j(x - p_2) > 2a_ip_2 + 2b_i(x - p_2) + 2a_jp_1 + 2b_j(x - p_1)
⇒aip1−bip1+ajp2−bjp2>aip2−bip2+ajp1−bjp1\Rightarrow a_ip_1 - b_ip_1 + a_jp_2 - b_jp_2 > a_ip_2 - b_ip_2 + a_jp_1 - b_jp_1
⇒ai(p1−p2)+bi(p2−p1)>aj(p1−p2)+bj(p2−p1)\Rightarrow a_i(p_1 - p_2) + b_i(p_2 - p_1) > a_j(p_1 - p_2) + b_j(p_2 - p_1)
⇒(ai−bi)(p1−p2)>(aj−bj)(p1−p2)\Rightarrow (a_i - b_i)(p_1 - p_2) > (a_j - b_j)(p_1 - p_2)
⇒ai−bi>aj−bj\Rightarrow a_i - b_i > a_j - b_j

回复

共 0 条回复，欢迎继续交流。

正在加载回复...