关于贪心邻项交换算法中的不等式
  • 板块学术版
  • 楼主Zyque
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/7/4 00:21
  • 上次更新2023/11/6 23:42:00
查看原帖
关于贪心邻项交换算法中的不等式
116063
Zyque楼主2020/7/4 00:21

不太会处理带min或max的不等式。例如国王游戏那道题中由max(bj,aibi)<max(ajbj,bi)\max(b_j,a_ib_i)<\max(a_jb_j,b_i)得到aibi<ajbja_ib_i<a_jb_j,我是这样想的:因为bj<ajbjb_j<a_jb_j,所以只需要比较aibia_ib_imax(ajbj,bi)\max(a_jb_j,b_i);因为aibi>bia_ib_i>b_i,所以要使aibi<max(ajbj,bi)a_ib_i<\max(a_jb_j,b_i),一定有aibi<ajbja_ib_i<a_jb_j。感觉这种方法只适用于简单的情况,有没有更好的方法?

我找到的一个方法是画图,对每个偏序关系画一条边,然后用反证法证明结论。本质上只是利用画图让证明更加浅显。所以您们都是怎么推导的,有没有相关的公式?

第二次发帖,还没人理我的话我自己爬

2020/7/4 00:21
加载中...