Форум программистов, компьютерный форум CyberForum.ru

Определить количество инверсий в массиве (таких пар элементов, в которых большее значение находится слева от меньшего). - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 5.00
RAMON@
0 / 0 / 0
Регистрация: 07.11.2009
Сообщений: 67
16.01.2010, 13:10     Определить количество инверсий в массиве (таких пар элементов, в которых большее значение находится слева от меньшего). #1
спасибо
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2010, 13:10     Определить количество инверсий в массиве (таких пар элементов, в которых большее значение находится слева от меньшего).
Посмотрите здесь:

определить количество инверсий в массиве Х т.е таких пар элементов, в которых большее число находится слева от меньшего:Xi>Xj при i<j. C++
Найти пары соседних элементов последовательности, среднее арифметическое которых равно N и количество таких пар. C++
C++ Вычислить Среднее арифм. значение элементов массива и число пар элементов которых сосед слева (т.е. индекс которого на 1 меньше) больше по величине
C++ Определить количество инверсий в целочисленном массиве
Определить количество инверсий в массиве C++
Найти количество пар элементов в которых на первом месте находится большее число C++
C++ В массиве найти количество пар соседних элементов в которых предыдущий элемент кратен следующему
C++ Количество элементов, значение которых меньше среднего арифметического в массиве

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
16.01.2010, 14:29     Определить количество инверсий в массиве (таких пар элементов, в которых большее значение находится слева от меньшего). #2
C++
1
2
3
4
5
int m[n];//n - размерность массива
int counter=0;
//заполнение массива
for (int i=0;i<n-1;i++) if (m[i] > m[i+1])counter++;
cout << counter;
guestonearth
3 / 3 / 2
Регистрация: 18.03.2010
Сообщений: 12
27.03.2010, 23:50     Определить количество инверсий в массиве (таких пар элементов, в которых большее значение находится слева от меньшего). #3
хехе)
Это веселенькая задача
за квадрат до тысячи элементов - это ясно а вот мой код для 50000 тысяч
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
 
typedef long long i64;
using namespace std;
 
class FenwickTree{
 
    public:
 
        vector<int> data;
 
        FenwickTree(int n) : data(n+1 , 0)
        {
        }
 
        inline void add(int numb,int val){
 
            for(int i = numb;i<data.size(); i+=i&(-i)){
                data[i]+=val;
            }
        }
 
        inline int sum_p(int end){
            int res=0;
 
            for(int i = end;i>0;i-=i&(-i)){
                res+=data[i];
            }
 
            return res;
        }
 
        inline int sum_d(int l, int r){
            return sum_p(r)-sum_p(l-1);
        }
 
 
};
 
//int numb[200000],inv[200000];
 
int main(){
    int t;
    scanf("%d",&t);
    
    for(int co=0;co<t;co++){ // количество тестов
 
        int numb_t,cur;
        i64 res=0;
        scanf("%d",&numb_t);// количество элементов в перестановке
        vector<int> numbs(numb_t);
 
        for (int i=0;i<numb_t;i++){
            scanf("%d",&numbs[i]);
        }
 
        vector<int> numb_s=numbs;
 
        sort(numb_s.begin(),numb_s.end());
 
        map<int,int> rev;
 
        for (int i=0;i<numb_t;i++)  rev[numb_s[i]] = i+1;
        
        for (int i=0;i<numb_t;i++) numbs[i] = rev[numbs[i]];
 
        FenwickTree x(numb_t);
 
        for (int i=0;i<numb_t;i++){
            
            int cur = numb_t + 1 - numbs[i];
            res+=x.sum_p(cur - 1);
            x.add(cur,1);
        }
 
        printf("%lld\n", res);
 
    }
 
    return 0;
}
класс реализующий дерево фенвика + масштабирование

Enjoy.....
Yandex
Объявления
27.03.2010, 23:50     Определить количество инверсий в массиве (таких пар элементов, в которых большее значение находится слева от меньшего).
Ответ Создать тему
Опции темы

Текущее время: 16:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru