Решение задачи на merge_sort на с++

319
28 июля 2022, 11:40

Возникли проблемы со следующей задачей:

Добавочное условие: в решении нужно использовать сортировку слиянием. Но есть проблемы с тем, чтобы при сортировке вместе с числами переставлять и их номера. Знаю, что есть std::pair, использую именно его, но все равно не получается. Код прилагаю:

#include <iostream>
#include <vector>
#include <string>
using namespace std;
void merge(vector <pair<int, int>> &a, int l, int m, int r) {
    int i, j, k, nl, nr;
    nl = m - l + 1;
    nr = r - m;
    vector <int> larr(nl), rarr(nr);
    for (i = 0; i < nl; i++)
        larr[i] = get < 0 > (a[l + i]);
    for (j = 0; j < nr; j++)
        rarr[j] = get < 0 > (a[m + 1 + j]);
    i = 0;
    j = 0;
    k = l;
    while (i < nl && j < nr) {
        if (larr[i] <= rarr[j]) {
            a[k] = make_pair(larr[i], i + 1);
            i++;
        }
        else {
            a[k] = make_pair(rarr[j], nl + j + 1);
            j++;
        }
        k++;
    }
    while (i < nl) {
        a[k] = make_pair(larr[i], i + 1);;
        i++; 
        k++;
    }
    while (j < nr) {
        a[k] = make_pair(rarr[j], nl + j + 1);
        j++; 
        k++;
    }
}
void mergesort(vector <pair<int, int>> &a, int l, int r) {
    int m;
    if (l < r) {
        m = l + (r - l) / 2;
        mergesort(a, l, m);
        mergesort(a, m + 1, r);
        merge(a, l, m, r);
    }
}
int main() {
    int n, b, min = 999999999, it1, it2, ftp1, ftp2;
    cin >> n;
    vector <pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> b;
        a[i] = make_pair(b, i + 1);
    }
    mergesort(a, 0, n - 1);
    for (int i = 1; i < a.size(); i++) {
        if (abs(get < 0 >(a[i]) - get < 0 >(a[i - 1])) < min) {
            min = get < 0 >(a[i]) - get < 0 >(a[i - 1]);
            ftp1 = get < 0 >(a[i]);
            ftp2 = get < 0 >(a[i - 1]);
            it1 = get < 1 >(a[i]);
            it2 = get < 1 >(a[i - 1]);
        }
    }
    cout << min << endl;
    if (ftp1 > ftp2) {
        cout << it2 << " " << it1;
        return 0;
    }
    else {
        cout << it1 << " " << it2;
        return 0;
    }
}

Например, на тесте из условия получаю 1 4 1. Подскажите, пожалуйста, как исправить.

Answer 1

std::merge решает проблему.

// g++ -Wall -Wextra -std=c++11 merge_sort.cpp
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using T = std::vector<std::pair<int, int>>;
void merge(T::iterator begin, T::iterator middle, T::iterator end) {
    T buffer(begin, middle);
    std::merge(buffer.begin(), buffer.end(), middle, end, begin);
}
void merge_sort(T::iterator begin, T::iterator end) {
    if (begin == end || begin + 1 == end) {
        return;
    }
    T::iterator middle = begin + (end - begin) / 2;
    merge_sort(begin, middle);
    merge_sort(middle, end);
    merge(begin, middle, end);
}
void print(const T &a) {
    for (const auto &v : a) {
        std::cout << v.first << '(' << v.second << ") ";
    }
    std::cout << '\n';
}
int main() {
    std::vector<int> v = {50, 10, 30, 60, 40, 20};
    T a;
    for (size_t i = 0; i < v.size(); ++i) {
        a.push_back(std::make_pair(v[i], i));
    }
    print(a);
    merge_sort(a.begin(), a.end());
    print(a);
}
Answer 2

а такое решение устраивает?

вариант 1:

const std::vector<int> nums = { 10, 3, 6, 2, 5 };
std::vector<std::pair<int, int>> objects;
for (int i = 0; i < nums.size(); i++)
    objects.push_back(std::pair<int, int>(nums[i], i));
std::sort(std::begin(objects), std::end(objects), [](const auto& obj1, const auto& obj2) {return obj1.first > obj2.first; });
int distance_min = -1;
int index_min;
for (int i = 0; i < objects.size() - 1; i++) {
    const int distance = objects[i].first - objects[i + 1].first;
    if ((distance < distance_min) || (distance_min == -1)) {
        distance_min = distance;
        index_min = i;
    }
}
std::cout << objects[index_min + 1].second << " " << objects[index_min].second << std::endl;

вариант 2:

const std::vector<int> nums = { 10, 3, 6, 2, 5 };
std::vector<int> indeces;
for (int i = 0; i < nums.size(); i++)
    indeces.push_back(i);
std::sort(std::begin(indeces), std::end(indeces), [nums](const int index1, const int index2) {return nums[index1] > nums[index2]; });
int distance_min = -1;
int index_min;
for (int i = 0; i < indeces.size() - 1; i++) {
    const int distance = nums[indeces[i]] - nums[indeces[i + 1]];
    if ((distance < distance_min) || (distance_min == -1)) {
        distance_min = distance;
        index_min = i;
    }
}
std::cout << indeces[index_min + 1] << " " << indeces[index_min] << std::endl;
READ ALSO
установка sfml под atom
c++

установка sfml под atom

Просьба подсказать как работать с sfml под atom:

 392
SFML: Многопоточная отрисовка Спрайтов
c++

SFML: Многопоточная отрисовка Спрайтов

Подскажите пожалуйста, как отрисовать спрайт, с использованием потоков в SFML?

 326
При наследовании от виртуального класса, компилятор выдает ошибку
c++

При наследовании от виртуального класса, компилятор выдает ошибку

Пытаюсь наследоваться от виртуального класса, компилятор выдает следующую ошибку:

 315
Не работает merge stl
c++

Не работает merge stl

У меня есть класс Patient и два вектора, которые содержат экземпляры этого класса, patients и newPatientsЯ хочу объединить их в один вектор fullListOfPatients с помощью...

 349