Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Контейнерные классы https://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;
C++ Как достать указатель на объект из контейнера set
Имеется вот такой код #include "stdafx.h" #include <string> #include <iostream> #include <fstream> #include <set> #include <conio.h> using namespace std;
C++ Значение указателей (*ptr.) на пустые ячейки памяти Здравствуйте, уважаемые форумчане! С началом изучения С++ стало возникать множество вопросов. Когда резервируется свободная память некоторого типа, то значения указателей к этим ячейкам выглядят... https://www.cyberforum.ru/ cpp-beginners/ thread630426.html
C++ Указатель на массив указателей на объекты, передать в метод объекта https://www.cyberforum.ru/ cpp-beginners/ thread630423.html
Здравствуйте! Нужно решить задачу, есть такой класс. class MyClsDisk { public: void SetDiskOnPurpose(MyClsDisk *p,int ix, MyClsDisk **a) { ...
C++ Адресное пространство
Адрес в сипп является 4байтным числом. Возможно ли модифицировать адрес так, что бы залезть в другие процессы? Или для каждого процесса выделяется "локальное" адресное пространство?
Интерфейс в VS2010 C++
:facepalm:При программировании хочу видеть описание типов, помниться мне что была какая та такая форма интересная например выбераешь мышкой структуру WNDCLASS например и в форме в низу ее свойства...
C++ Как исправлять ошибку? я из книжки выписал первую программу #include <iostream> int main() { cout << "Hello World!\n"; return 0; } компилятор сказал что надо из iostream.h убрать .h что я и сделал но... https://www.cyberforum.ru/ cpp-beginners/ thread630392.html
C++ Указатель на функцию https://www.cyberforum.ru/ cpp-beginners/ thread630387.html
Столкнулся с проблемой передачи функции в функцию как переменной. Не могли бы вы объяснить мне эту тему? Компилятор ругается даже на: void z() { }
C++ Диаграммы в С++ Задача. Даны десять числовых величин. Принимая их сумму за 100 %, построить по выбору пользователя либо круговуб диаграмму, либо столбчатую, показывающую процентное соотношение между данными... https://www.cyberforum.ru/ cpp-beginners/ thread630386.html
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 38
0

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

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