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

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

Восстановить пароль Регистрация
 
R_e_n
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 35
30.07.2012, 01:30     Ошибка в подсчете количества инверсий #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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.07.2012, 01:30     Ошибка в подсчете количества инверсий
Посмотрите здесь:

Ошибка в подсчете площади треугольника C++
Определить количество инверсий в последовательности C++
Подсчет кол-ва инверсий C++
Найти количество итераций при подсчете суммы ряда C++
C++ Определить количество инверсий в целочисленном массиве
Не могу найти ошибку в подсчете значения функции и разложения ее по ряду C++
Определить количество инверсий в массиве C++
Исправить мелкую ошибку в подсчете листьев деревьев C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
R_e_n
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 35
31.07.2012, 11:14  [ТС]     Ошибка в подсчете количества инверсий #2
Написал программу работающую за n*n и программу сравнивающую результаты несколько раз запускал для 100000 случайных массивов, результаты одиннаковые.
Пробовал перебирать всевозможные массивы, но их там очень много. Программа долго работала но ничего не нашла.

Переписал на Делфи, так же выдало ошибку на 12 тесте.

Посоветуйте хотя бы как еще можно проверить

Добавлено через 42 минуты
А все решил

int на long long поменял везде=)
Yandex
Объявления
31.07.2012, 11:14     Ошибка в подсчете количества инверсий
Ответ Создать тему
Опции темы

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