Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
R_e_n
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 38
#1

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

30.07.2012, 01:30. Просмотров 543. Ответов 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
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.07.2012, 01:30
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Ошибка в подсчете количества инверсий (C++):

Что нужно изменить чтобы при подсчете количества обменов программа подсчитывала не один алгоритм сортировки - C++
#include &lt;stdio.h&gt; //Подключение заголовочного файла библиотеки ввода/вывода #include &lt;locale.h&gt; //Подключение заголовочного файла...

Ошибка в подсчете, цикл for - C++
#include &lt;iostream&gt;// подключили библиотеку ввода-вывода #include &lt;cstdlib&gt;// подключили библиотеку для роботы с функцией system using...

Ошибка в подсчете площади треугольника - C++
//main.cpp int a,b,c; a=b=c=0; cin&gt;&gt;a&gt;&gt;b&gt;&gt;c; cout&lt;&lt;eqS(a,b,c); int eqS(int a,int b,int c){ int...

Задача о подсчете треугольников - C++
Добрый вечер, вообщем есть такая задачка: Есть ряд треугольников построены таким образом: первый это правильный треугольник с вершиной...

Подсчет кол-ва инверсий - C++
Здравствуйте, помогите разобраться с ошибкой. Компилирую код, а компилятор (VS 2010 ) выдает ошибку, не могу понять что делать. ...

Перестановка с вектором инверсий - C++
Здравствуйте,помогите перестроить программу с паскаля на с++ вот с этой темы http://www.cyberforum.ru/pascalabc-net/thread1840723.html Я...

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

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

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

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

int на long long поменял везде=)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.07.2012, 11:14
Привет! Вот еще темы с ответами:

Найти ошибку при подсчете суммы ряда - C++
Помогите найти ошибку, выдает неправильный результат. Задан массив z(m). Посчитать: #include &lt;iostream&gt; #include &lt;cmath&gt; ...

Исправить мелкую ошибку в подсчете листьев деревьев - C++
int list(node *t) { return (1+(t-&gt;l ? list(t-&gt;l):0)+(t-&gt;r ? list(t-&gt;r))); } Ошибки: ошибка: expected ':' before ')'...

Определить количество инверсий в последовательности - C++
Одномерные массивы Дана последовательность из n целых чисел. Определить количество инверсий в этой последовательности (т.е. таких пар...

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


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

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

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