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

Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Найти сумму ряда http://www.cyberforum.ru/cpp-beginners/thread1210081.html
Здравствуйте уважаемые форумчане! Нуждаюсь в помощи. Имеется ряд http://firepic.org/images/2014-06/16/4mby1f0q9sec.png Необходимо найти его сумму. Visual C++, консольное приложение. Желательно...
C++ Алгоритм Фибоначчи Пользователь вводит любые два числа и количество операций, программа должна два числа сложить и результат записать в конец, после сложить два последних числа и так же записать в конец, и так... http://www.cyberforum.ru/cpp-beginners/thread1210048.html
Блок-схемы C++
Кто может нарисовать 7 блок-схем, не сложные по видимому, но надо поскорее кто сечет отпишите плиз
C++ Набор инструментов для инди с мультиплеером по ip
Подскажите какие библиотеки подключать для создания игр в стиле контры, марио, battle toads... Только с поддержкой качественной графики и возможностью игры с аппонентами через локальную сеть,...
C++ Сохранение результатов в текстовый документ http://www.cyberforum.ru/cpp-beginners/thread1210039.html
Добрый день. Нужна помощь, в данный код нужно добавить возможность сохранения результатов в текстовый документ. #include <iostream> using namespace std; int main() { double x, y, o; ...
C++ Библиотеки glut.lib и glut32.lib не могу найти Здравствуйте товарищи, помогите с очередной дилеммой. На днях начал изучать программирование, скачал Dav C++, но для дальнейших уроков нужны библиотеки - glut.h , glut32.blut , glut.bll , glut32.lib.... подробнее

Показать сообщение отдельно
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
17.06.2014, 13:14
вот попробуй пошли вот это!
я там ее еще дебагал поэтому дофига комментов!
я не уверен что правильно, но просто интересно проверить!


UPD::
да это верно! я на другом сайте послал - полное решение!))

C++ (Qt)
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <iostream>
#include <vector>
 
using namespace std;
 
const int dxh[] = {-2, -2, 2, 2, -1, -1, 1, 1};
const int dyh[] = {-1, 1, -1, 1, -2, 2, -2, 2};
 
long long int inv = 0;
int a[555555], b[555555];
int n;
 
void merge(int l, int r)
{
    //cout << "ranges == " << l << ' ' << r << endl;
    int sz = r - l + 1;
    if(sz == 1)
        return;
    if(sz == 2)
    {
        if(a[l] > a[r])
        {
            int t = a[l];
            a[l] = a[r];
            a[r] = t;
            inv++;
        }
 
        return;
    }
 
    int mid = sz / 2;
    
    //vector<int> b, c;
 
    merge(l, l + mid - 1);
    merge(l + mid, r);
 
    //for(int i = mid; i < a.size(); i++)
        //c.push_back(a[i]);
 
    //vector<int> a1 = merge(b);
    //vector<int> a2 = merge(c);
 
    //int n = l + mid - 1 - l + 1;
    //int m = r - (l + mid) + 1;
 
    //vector<int> s;
 
    /*cout << "first vector == " << endl;
    for(int i = 0; i < n; i++)
        cout << a1[i] << ' ';
    cout << endl;
 
    cout << "second vector == " << endl;
    for(int i = 0; i < m; i++)
        cout << a2[i] << ' ';
    cout << endl;*/
 
    //int sz1 = (n - 1) - l + 1;
    int n = l + mid;
    int m = r + 1;
    /*int sz1 = (n - 1) - l + 1;
 
    cout << "befor sliv == " << endl;
    for(int i = l; i < n; i++)
        cout << a[i] << ' ';
    cout << endl;
    for(int i = l + mid; i < m; i++)
        cout << a[i] << ' ';
    cout << endl;*/
    int i = l, j = l + mid;
    //cout << "segments == " << i << ' ' << n - 1 << ' ' << j << ' ' << m - 1 << endl;
 
    int id = 0;
    long long cur = 0;
 
    while(i < n || j < m)
    {
        //cout << i << ' ' << j << endl;
        if(i < n)
        {
            if(j >= m || a[i] <= a[j])
            {
                b[id] = a[i];
                id++;
                //s.push_back(a[i]);
                i++;
            }
            else
            {
                b[id] = a[j];
                id++;
                //s.push_back(a[j]);
                j++;
                inv += (n - 1) - i + 1;
                cur += (n - 1) - i + 1;
                
            }
        }
        else
        {
            b[id] = a[j];
            id++;
            //s.push_back(a[j]);
            j++;
        }
    }
 
    int idx = 0;
    for(int i = l; i <= r; i++)
        a[i] = b[idx], idx++;
 
    /*cout << "after sliv == " << endl;
    for(int i = l; i <= r; i++)
        cout << a[i] << ' ';
    cout << endl;
    cout << "cur == " << cur << endl;*/
 
    //return s;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    int val = 1000000;
    for(int i = 0; i < n; i++)
    {
        int ch;
        scanf("%d", &ch);
        //ch = val;
        val--;
        a[i] = ch;
    }
 
    /*cout << "begin" << endl;
    for(int i = 0; i < n; i++)
        printf("%d ", a[i]);
    cout << endl;*/
    //vector<int> res = merge(mas);
    merge(0, n - 1);
 
    /*cout << "res == " << endl;
    for(int i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");*/
    printf("%lld\n", inv);
    return 0;
}
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru