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

Ошибка в подсчете количества инверсий - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Контейнерные классы http://www.cyberforum.ru/cpp-beginners/thread630506.html
Есть некоторое сомнения, помоготи пожалуйста: Если у меня есть например такой код: vector<int> * pmyvec; pmyvec->push_back(3); pmyvec->push_back(4); delete pmyvec; Есть ли в этом коде утечка памяти?
C++ Обьяснить программу (Принципи ее работы) Здравствуйте! Есть программа: #include <stdio.h> #include <memory.h> struct arrInt { char * data; int length; http://www.cyberforum.ru/cpp-beginners/thread630498.html
C++ Как достать указатель на объект из контейнера set
Имеется вот такой код #include "stdafx.h" #include <string> #include <iostream> #include <fstream> #include <set> #include <conio.h> using namespace std;
C++ Значение указателей (*ptr.) на пустые ячейки памяти
Здравствуйте, уважаемые форумчане! С началом изучения С++ стало возникать множество вопросов. Когда резервируется свободная память некоторого типа, то значения указателей к этим ячейкам выглядят весьма интересно. Вот пример. #include "stdafx.h" #include <iostream> #include <limits.h>
C++ Указатель на массив указателей на объекты, передать в метод объекта http://www.cyberforum.ru/cpp-beginners/thread630423.html
Здравствуйте! Нужно решить задачу, есть такой класс. class MyClsDisk { public: void SetDiskOnPurpose(MyClsDisk *p,int ix, MyClsDisk **a) { cout<<(*p).Weight<<endl;
C++ Адресное пространство Адрес в сипп является 4байтным числом. Возможно ли модифицировать адрес так, что бы залезть в другие процессы? Или для каждого процесса выделяется "локальное" адресное пространство? подробнее

Показать сообщение отдельно
R_e_n
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 35

Ошибка в подсчете количества инверсий - C++

30.07.2012, 01:30. Просмотров 520. Ответов 1
Метки (Все метки)

Здравствуйте, помогите разобраться с подсчетом количества инверсий, в случае повторяющихся элементов. Количество элементов в массиве 65537, максимальное значение 10^9, элементы не отрицательные, время 0.5 с.

Гуглил, нагуглил три алгоритма (http://cppalgo.blogspot.com/2011/02/blog-post_07.html), но там случай различных элементов. Написал первый алгоритм

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
#include <iostream>
#include <vector>
 
using namespace std;
 
int merge(vector<int> &a, int l, int m, int r)
{
    int amount = 0;
    vector<int> buffer(r - l + 1);
    int indexL = l;
    int indexR = m + 1;
    int indexBuf = 0;
    while (indexL <= m && indexR <= r)
    {
        if (a[indexL] <= a[indexR])
            buffer[indexBuf++] = a[indexL++];
        else
        {
            amount += m - indexL + 1;
            buffer[indexBuf++] = a[indexR++];
        }
    }
    while (indexL <= m)
        buffer[indexBuf++] =  a[indexL++];
    while (indexR <= r)
        buffer[indexBuf++] =  a[indexR++];
 
copy(buffer.begin(),buffer.end(),a.begin()+l);
    return amount;
}
 
int merge_sort(vector<int> &a, int l, int r)
{
    int amount = 0;
    if (l == r)
        return amount;
 
    int m = (l + r) / 2;
    amount += merge_sort(a, l, m);
    amount += merge_sort(a, m+1, r);
    amount += merge(a, l, m, r);
 
    return amount;
}
 
int main()
{
    #ifdef _DEBUG
        freopen("input.txt","r",stdin);
    #endif
 
    vector<int> a;
    int N;
    cin >> N;
 
    a.resize(N);
    for (int indexA = 0; indexA < N; indexA++)
        cin >> a[indexA];
 
    int amount = merge_sort(a, 0, N-1);
    cout << amount;
 
    return 0;
}
Чуть исправил, отправил решение, выдало ошибку. Долго я бился. Так и не нашел ее.

Второе решение - карманная сортировка. С учетом того что макс значение 10^9 карманы получились или большие или их много. По времени не прошло.

Третье решение, я так и не смог додуматься как модифицировать дерево Фенвика, для случая дубликатов.

Если что вот задача http://acm.sgu.ru/problem.php?contest=0&problem=180
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru