为什么以a为关键字对b排序,再求逆序对是错误做法
查看原帖
为什么以a为关键字对b排序,再求逆序对是错误做法
762588
Edgebright楼主2023/7/7 14:35

如题,推式子之后不难发现要消除所有ai<aja_i<a_j 且 bi>bjb_i > b_j的火柴,由于每次交换能且仅能消除一对,所以ai<aja_i<a_j 且 bi>bjb_i > b_j的火柴对数就是答案,做二维偏序既可,但这是错误的(会得10分的好成绩)

这个做法是最优性错误还是正确性错误?为什么是错误的?有大佬说按a排序会改变火柴的相邻关系,但是按上面结论,按a排序似乎不影响二维偏序关系?

2023/7/7 14:35
加载中...