感觉这道题目有问题?
查看原帖
感觉这道题目有问题?
1209877
Vector_Li楼主2024/10/31 21:56

想求助一个问题:

https://www.luogu.com.cn/discuss/444636 这个帖子里提到了一个反例。

已知:

  • A>aA > a
  • B>bB > b
  • A,B,a,bA, B, a, b 都是 1 或 2 或 3

我们知道一定有 A+B>a+bA + B > a + b

移项,Ab>aBA - b > a - B 一定成立,这没有问题。

但是,如果我们直接说,Ab>aBA - b > a - B 当且仅当 min(Ab)>max(aB)\min(A - b) > \max(a - B),显然是错误的啊。

因为 min(Ab)=0,max(aB)=0\min(A - b) = 0, \max(a - B) = 0 (枚举一下所有可能的情况就可以得出)。

我想了一下,为什么两者不等价。我认为,是因为 min(Ab)\min(A - b)max(aB)\max(a - B) 是互相影响的。

但是,如果我们把不等式变形成 Aa>bBA - a > b - B,然去算 min,max\min, \max,结果又对了?

所以想问一下大家,为什么题解的做法是正确的。也就是说,为什么枚举两种可能的不等式变形情况,然后去算全局的、会互相影响的 min,max\min, \max 并比较的算法是正确的。思考无果,我个人也举不出反例。谢谢。

2024/10/31 21:56
加载中...