순위 순서 목록의 최대 합계

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) 항목의 또 다른 목록이지만 다른 점을 가지므로 다른 순위를 갖습니다. 두 목록의 항목 순위 차이의 합계와 같이이 두 목록을 비교하려고합니다. 차이 S의 = (항목 1 순위 차이 + 항목 2 ""+ ....)의

이 경우

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 = 3 + 1 + 0 + 2 = 6

예 :

최악의 경우와 비교하기 위해

, 나는 다른 N의이 합 최악의 값이 필요합니다.

때문에, N의 관점에서 S의 최대 값은 무엇인가? S_max (N) =?

도움 주셔서 감사합니다.

Answer 1

나는 이해 모르겠지만, 길이 N의이 개 목록에 대한 최악의 값은 1 위를 기록 목록 1에있는 모든 항목 목록 이주 동일 순위 (안 유일한 최악의 경우 어떤 항목이 될 것이지만, 확실히 최악의 경우) :

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