Что такое быстрый способ сравнить большой список пар целых чисел?

Question

Дело в том, мы имеем N пар целых чисел, в качестве примера:

Мы говорим, что одна пара больше другой, если оба числа из одной пары больше, чем две другие, или если первое число равно, а другое - больше или наоборот. В противном случае, если вы не можете сравнить их таким образом, то вы не можете установить, какой из них больше.

Идея состоит в том, чтобы знать, для каждой пары, сколько пар больше (в примере первая пара больше третьей и последней, поэтому ответ для первого равен 2). Тривиальным решением будет O (n^2), который просто сравнивает каждую пару со всеми остальными и добавляет один к счетчику для каждого положительного совпадения.

Может ли кто-нибудь придумать более быструю идею? Благодаря!

---

Я выполнил простое решение (N^2), работает чтение с "sumos.in":

#include <iostream> 
#include <fstream> 

#define forn(i, x, N) for(i=x; i<N; i++) 

using namespace std; 

ifstream fin("sumos.in"); 
ofstream fout("sumos.out"); 

struct sumo{ 
    int peso, altura; 
}; 

bool operator < (sumo A, sumo B) { 
    if(A.altura == B.altura) 
     if(A.peso < B.peso) 
      return true; 
     else 
      return false; 
    else 
     if(A.peso == B.peso) 
      if(A.altura < B.altura) 
       return true; 
      else 
       return false; 
     else 
      if((A.altura < B.altura) && (A.peso < B.peso)) 
       return true; 
      else 
       return false; 
} 

int L; 
sumo T[100000]; 
int C[100000]; 

int main() 
{ 
    int i, j; 
    fin >> L; 

    forn(i, 0, L) 
     fin >> T[i].peso >> T[i].altura; 

    forn(i, 0, L) 
     forn(j, 0, L) 
      if(j!=i) 
       if(T[j]<T[i]) 
        C[i]++; 

    forn(i, 0, L) 
     fout << C[i] << endl; 

    return 0; 
} 

Пример ввода:

10 
300 1500 
320 1500 
299 1580 
330 1690 
330 1540 
339 1500 
298 1700 
344 1570 
276 1678 
289 1499 

Выходы:

1 
2 
1 
6 
3 
3 
2 
5 
0 
0 

---

Я решил эту проблему, используя дерево сегментов. Если вы хотите увидеть реализацию: http://pastebin.com/Q3AEF1WY

Answer 1

Вы можете использовать. Сортировка. например

int z = {23,65,45, 66,22,65,80,20,30,11,11, 20}; 

int i, j, k, tmp;

for (i=1; i<n; i++){ 
    j= n-i-1; 

    for (k=0; k<=j; k++) 

// Обратите внимание на этот блок.

 if (z[k]>z[k+1]){ 
      tmp= z[k]; 
      z[k]= z[k+1]; 
      z[k+1]= tmp; 
     } 
} 

Answer 2

Я думаю, что я придумал решение, но это довольно сложно. Основная идея заключается в том, что есть такие группы, где пары могут быть расположены в доминированной порядке, например:

11 20 30 11 
22 65 80 20 
23 65 
45 65 

Если вы начинаете думать о принятии ваши пары и пытаются создать эти группировки вы понимаете, что вы будете в конечном итоге с дерево структура. Например представьте, что мы добавили пару 81 19 в список и добавить пару (-∞, -∞)

 (-∞, -∞) 
    / \ 
11 20  30 11 ---\ 
22 65  80 20 81 19 
23 65 
45 65 

Если следовать по пути от узла к корню вы будете считать, сколько пар текущей пары доминирует.В этом примере это похоже на то, что вы можете использовать бинарный поиск, чтобы выяснить, куда вставить пару в структуру. Здесь начинаются сложности. Вы не можете выполнять двоичный поиск/вставку в связанном списке. Однако есть очень аккуратная структура данных, называемая skip list, которую вы можете использовать. Вы можете в основном выполнить поиск и вставить время O (logn).

Есть еще одна проблема. Что, если есть тонны этих группировок? Представьте себе список, как

11 20 
12 19 
13 18 
14 17 

Ты древовидная структура будет выглядеть следующим образом:

  (-∞, -∞) 
    / /  \  \ 
11 20 12 19 13 18 14 17 

Снова используйте списки пропуска для заказа этих узлов. Я думаю, для этого потребуются два разных типа узлов в дереве: горизонтальный тип, подобный выше, и вертикальный тип, как в первых примерах. Когда вы закончите строить дерево, выполните итерацию дерева с помощью DFS при записи текущей глубины, чтобы связать каждую пару с количеством узлов, в которых она доминирует.

Если приведенный выше алгоритм верен, вы можете вставить пару в дерево в O (logn) и, следовательно, все пары в O (nlogn). Часть DFS примет время O (n), таким образом, построение дерева и объединение пары с числом, в котором она доминирует, займет время O (nlogn). Вы можете сортировать пары в зависимости от количества доминантов в O (nlogn), поэтому весь процесс займет время O (nlogn).

Опять же, возможно, есть более простой способ сделать это. Удачи!