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

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

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

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

30.07.2012, 01:30. Просмотров 525. Ответов 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     Ошибка в подсчете количества инверсий
Посмотрите здесь:

Ошибка в подсчете, цикл 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++
Здравствуйте,помогите перестроить программу с паскаля на с++ вот с этой темы http://www.cyberforum.ru/pascalabc-net/thread1840723.html Я...

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

Найти ошибку при подсчете суммы ряда - 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++
Помогите пожалуйста Дан линейный неупорядоченный массив А, состоящий из 20 целых чисел. Составить программу, которая определяет...

Определить колличество инверсий в последовательности - C++
Даны натуральное число n (n&lt;=100). целые числа a1, .... an. Определить колличество инферсий в этой последовательности, т.е. таких пар...

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


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

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

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

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

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

int на long long поменял везде=)
Ответ Создать тему
Опции темы

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