题解有误
  • 板块P6074 最小路径
  • 楼主Yu_Jie
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/10/10 15:23
  • 上次更新2023/11/2 14:40:17
查看原帖
题解有误
217452
Yu_Jie楼主2023/10/10 15:23

第二篇题解的贪心做法基于以下结论:

显然对于一个向量 a⃗\vec a,如果存在另外两个向量 b⃗\vec b 和 c⃗\vec c,满足 b⃗\vec b 的斜率小于 c⃗\vec c 的斜率,那么 a⃗+b⃗\vec a+\vec b 的斜率也会小于 a⃗+c⃗\vec a+\vec c 的斜率。

显然该结论是错误的。Hack 数据:

4 2
3 2 5 9
4 6 1 2
1 2
2 3
2 4
2023/10/10 15:23
加载中...