"토너먼트"를위한 더 나은 알고리즘

Question

질문이 있습니다. 저는 며칠이 지난 지금부터 ZCO를 준비해 왔으며 3 초의 제한 시간 내에 해결할 수 없었던 아주 간단한 문제를 겪었습니다. 여기에 문제가 간다 :

N 팀은 서로 다른 팀의 각 쌍 정확히 한 번만 서로 연극 화성에 리그 크리켓 대회에 참여합니다. 따라서, (N × (N1))/2 개의 합계가 이다. 한 전문가가 각 팀에 힘을 양수로 할당했습니다. 이상하게도 화성인들은 편성 매치를 좋아하고 매치에서 얻은 광고 수익은 두 개의 힘의 차이 절대 값이 입니다. N 팀의 강점을 고려하면 모든 경기에서 총 광고 수익이 발생합니다.

예를 들어, N이 4이고 팀 1, 2, 3, 및 4의 팀 강점이 각각 3, 10, 3 및 5라고 가정합니다.

가

7, 0, 2, 7, 5, 2

따라서 총 광고 수익이 23

샘플 입력 4 3 10 3 : 다음과 같이 광고 수익 6 개에서 일치 은 5 샘플 출력 23 테스트 데이터 모든 하위 작업에서 각 팀의 강점은 1에서 1,000 사이의 정수입니다.

하위 작업 1 (30 자) : 2 ≤ N ≤ 1,000.
하위 작업 2 (70 자) : 2 ≤ N ≤ 200,000.

제한

시간 제한 : -3

메모리 제한 : SO 64메가바이트

, 나는 검사하고 해당 등 모든 팀의 광고 수익을 찾는 간단한 알고리즘에 대한 거부했습니다 그 전에 다른 모든 팀에게. 이 금액은 서브 작업 2를 통과하지 못하는 O (n^2)입니다.이 문제를 개선 할 수 있다고 생각하지 않습니다. 아무도 도와 줄 수 있습니까?

P. 도움이되지 않지만, 여기에 내 현재의 C 코드는 비록 :

#include <stdio.h> 

int main(void) 
{ 
    long long int n, i, j; 
    scanf("%lld", &n); 
    long long int A[n], strength = 0; 
    for(i = 0;i < n;i++) 
    { 
     scanf("%lld", &A[i]); 
     for(j = i;j >= 0;j--) 
     { 
      strength += A[i] > A[j] ? A[i] - A[j] : A[j] - A[i]; 
     } 
    } 
    printf("%lld\n", strength); 
    return 0; 
} 

Answer 1

한다고 가정 우리는 10 개 팀이, 약한에 강한에서 그들을 A, B, C, ..., J를 호출합니다. A와 J의 매치를 살펴 봅시다. 재미있는 속성이 있습니다. 해당 경기의 수익은 다른 두 경기 인 AB와 BJ의 수익 합계와 같습니다. 아, 그리고 또한 AC와 CJ. 그리고 ... 와우, AJ에 9를 곱하면 모든 경기의 수익 합계가 A 또는 J 중 하나입니다! 이제 겨우 8 팀이 남았습니다. B와 I의 경기를 살펴 봅시다. 흥미로운 속성이 있습니다 ... 수학이 훌륭하지 않습니까?