Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 38
1

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

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

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

Гуглил, нагуглил три алгоритма (http://cppalgo.blogspot.com/20... st_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?... roblem=180
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.07.2012, 01:30
Ответы с готовыми решениями:

Ошибка в подсчёте количества элементов List
Всем привет. Никак не могу понять, почему система выводит всегда разные значения в MessageBox ...

Ошибка в подсчете количества вхождений символа в строку
Подскажите пожалуйста, в чем ошибка? int _tmain(int argc, _TCHAR* argv) { char sym = 'a';...

Алгоритм для подсчета количества инверсий
Как построить алгоритм, который для перестановки чисел(любой) будет считать общее количество...

Подсчет общего количества инверсий в строке
Назовем инверсией в строке ситуацию Aij&gt;Aij+1 (в отлиции от ситуации Aij&lt;=Aij+1). Получим сассив...

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

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

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

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

int на long long поменял везде=)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
31.07.2012, 11:14

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Использование this при подсчете количества символов
Только учусь, потому вопрос из разряда &quot;для новичков&quot;. Задача. Необходимо посчитать количество...

Как упростить решение задачи о подсчете количества
Стояла задача: дан список учеников с фамилиями, именами, классом и баллами. Нужно найти максимумы...

Бесконечный цикл при подсчете количества строк!
Ситуация довольна странная. При подсчете строк в файле программа сваливается в бесконечный цикл. ...

Учет двух условий при подсчете количества объектов
Доброго времени суток! Возник следующий вопрос. нужно посчитать количество объектов,...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.