waP六感程序建设网站,营销型网站建设+课程,购物网站国外,网站二次开发是什么先来看看官方题解的做法#xff0c;他一反常态的没有在逆序对题目里面考虑每个位置的贡献#xff0c;而是直接回到定义考虑每对数是否是逆序对 我们考虑原数列中任意的一组数\((a_i,a_j)\)和\((b_i,b_j)\)。如果最开始两个都不是逆序对#xff0c;那么交换之后两个都是逆序对… 先来看看官方题解的做法他一反常态的没有在逆序对题目里面考虑每个位置的贡献而是直接回到定义考虑每对数是否是逆序对 我们考虑原数列中任意的一组数\((a_i,a_j)\)和\((b_i,b_j)\)。如果最开始两个都不是逆序对那么交换之后两个都是逆序对如果最开始两个都是逆序对那么交换之后两个都不是逆序对如果最开始一个是逆序对另外一个不是那么交换之后仍然如此 最后一种情况的一组数无论怎么交换他对答案的贡献都是不会变化的所以我们不用考虑而前面两种组合我们肯定要尽量的让交换后都不是逆序对的数量更多而这显然是可以达到的最后的序列中如果存在一组数\((a_i,a_j)\)和\((b_i,b_j)\)而且这两对数都是逆序对那么我们交换一下就好了 我们以\(a_i\)为关键字排序就可以数出来是满足题意的(当然这道题目放在B也应该猜到这么做) 再来看看我的证明仍然是考虑每一个位置的贡献 首先交换\(i\)\(j\)的操作肯定可以等价于交换若干次相邻的数对所以为了简化问题我们考虑每次操作交换相邻的两个数的情况 对\((a_i,a_{i1})\)和\((b_i,b_{i1})\)如果前者是逆序对但是后者不是我们交换之后总逆序对数不变如果两个都不是逆序对交换之后逆序对个数加二如果两个都是逆序对个数交换之后逆序对个数减二 也就是说对任意的序列如果把其按照\(a_i\)为关键字进行排序交换(像冒泡排序那样)那么每次的交换操作不会让总逆序对数增加可能会减少于是得证
