arrays - 排序列表中的最大总和

Question

我知道这不是一个编程问题，但它涉及编程和一些数学。假设我有一组N个项目，所有项目都有它们的点，并按它们的等级排序。例如：

list1 = { // N = 4
1: (item1, points: 100, rank:1), 
2: (item2, points:55, rank:2), 
3: (item3, points:55, rank:2),
4: (item4, points:45, rank:3) }

等等。list2 是这 4 (N) 个项目的另一个列表，但点数不同，因此排名不同。我正在尝试对这两个列表进行比较，例如两个列表中项目排名差异的总和。

例如：

list2 = { // N = 4
1: (item4, points: 10, rank:1), 
2: (item3, points:9, rank:2), 
3: (item2, points:8, rank:3),
4: (item1, points:7, rank:4) }

在这种情况下，差异总和 S = (item1 rank difference + item2 " " + ....) S= 3 + 1 + 0 + 2 = 6

为了将它与最坏的情况进行比较，我需要这个总和对于不同 N 的最差值。

那么，就 N 而言，S 的最大值是多少？S_max (N) =?

谢谢你的帮助。

score 0 · Accepted Answer

我不确定是否理解，但 2 个长度为 N 的列表的最差值将是列表 1 中的每个项目都排在第 1 位，并且列表 2 中没有项目共享相同的排名（不是唯一的最坏情况，但绝对是最坏的情况) :

sum = (1-1)+(2-1)+...+((n-1)-1)+(n-1)
    =  0 + 1 + ... + (n-2) + (n-1)
    = n(n-1)/2

1 回答 1