高分问一道算法题英文的哦SupposearrayAhasNelementsandistobesortedinascendingorder.ThismeansthatA[i]≤A[j],wheni

Question

高分 问一道算法题 英文的哦
Suppose array A has N elements and is to be sorted in ascending order. This means that
A[ i ] ≤ A[ j ], when i < j. Two elements of the array, A[ i ] and A[ j ], form an inversion if
A[ i ] > A[ j ] and i < j.
Now suppose array A is actually sorted in descending order and that A contains no duplicate
elements. If A[ i ] and A[ i + k ], where 0 ≤ i < N – k, and 0 < k < N are swapped, what is
the maximum number of inversions removed as an expression in k? Justify your answer.

Answer 1

Suppose array A has N elements and is to be sorted in ascending order.This means that 假设数组A有N个元素,他们是按非降序排列的.这就是说A[ i ] ≤ A[ j ],when i < j.Two elements of the array,A[ i ] and A...