Отображение первого элемента пользовательского ввода в массиве

Question

Мы можем определить термин «значение имени» как среднее положение букв в имени, рассчитав «А» как 1, «В» как 2, «С» как 3 и т. Д. ,Значение «BOB» будет (2 + 15 + 2) / 3 = 6. В соответствии с этим значением имена будут располагаться от наименьшего к наибольшему в выходных данных. Когда два или более имени имеют одинаковое значение, имя, которое находится на первой позиции в исходном списке (первое, которое вводит пользователь), должно отображаться первым в отсортированном списке (вывод).

Входные данные В первой строке у нас есть целое число N (1 <= N <= 100), которое является числом имен. В каждой из N строк у нас есть одно имя ([AZ], без пробелов). Имена содержат от 1 до 200 букв. </p>

Выходные данные Распечатайте отсортированный список (одно имя в строке).

Контрольный пример

Ввод: 3 BOB AAAAAAA TOM Выход:AAAAAAA BOB TOM

Я попытался что-то, и код, казалось, работал, у меня просто была проблема с выводом. Я не мог найти способ расположить имена с одинаковым значением в соответствии с их положением в исходном списке. Вот другой тестовый пример, который я пробовал, но не выяснил:

Input:


 10
 COSOPYILSPKNKZSTUZVMEERQDL
 RRPPNG
 PQUPOGTJETGXDQDEMGPNMJEBI
 TQJZMOLQ
 BKNGFEJZWMJNJLSTUBHCFHXWMYUPZM
 YNWEPZKNBOOXNZVWKIUS
 LV
 CJDFYDMYZVOEW
 TMHEJLIDEHT
 KGTGFIFWYTKPWTYQQPGKRRYFXN

Output:
TMHEJLIDEHT
PQUPOGTJETGXDQDEMGPNMJEBI
BKNGFEJZWMJNJLSTUBHCFHXWMYUPZM
CJDFYDMYZVOEW
RRPPNG
COSOPYILSPKNKZSTUZVMEERQDL
KGTGFIFWYTKPWTYQQPGKRRYFXN
TQJZMOLQ
YNWEPZKNBOOXNZVWKIUS
LV

My output:

TMHEJLIDEHT 
PQUPOGTJETGXDQDEMGPNMJEBI
CJDFYDMYZVOEW // these two
BKNGFEJZWMJNJLSTUBHCFHXWMYUPZM // should be arranged with their places switched
RRPPNG 
COSOPYILSPKNKZSTUZVMEERQDL 
KGTGFIFWYTKPWTYQQPGKRRYFXN 
TQJZMOLQ 
YNWEPZKNBOOXNZVWKIUS 
LV

#include <iostream>
#include <string>

using namespace std;

int main() {

int N;
cin >> N;

string words[N];

int res[N];

for (int i = 0; i < N; i++) {
    int sum = 0;
    int value = 0;
    int temp = 0;
    string word;
    cin >> words[i];
    word = words[i];
    for (int j = 0; j < word.length(); j++) {
        sum += (int)word[j] - 64;
    }
    value = sum / word.length();
    res[i] = value;
}

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (res[i] < res[j]) {
            swap(res[i], res[j]);
            swap(words[i], words[j]);
        }
    }
}

for (int i = 0; i < N; i++) {
    cout << words[i] << endl;
}

return 0;
}

Answer 1

Если вы используете std::multimap<int, std::string>, сортировка не понадобится, поскольку ключ уже будет служить критерием сортировки.

Вот решение с использованием std::multimap:

#include <string>
#include <numeric>
#include <iostream>
#include <sstream>
#include <map>

// Test data
std::string test = "10\n"
"COSOPYILSPKNKZSTUZVMEERQDL\n"
"RRPPNG\n"
"PQUPOGTJETGXDQDEMGPNMJEBI\n"
"TQJZMOLQ\n"
"BKNGFEJZWMJNJLSTUBHCFHXWMYUPZM\n"
"YNWEPZKNBOOXNZVWKIUS\n"
"LV\n"
"CJDFYDMYZVOEW\n"
"TMHEJLIDEHT\n"
"KGTGFIFWYTKPWTYQQPGKRRYFXN\n";

int main()
{
    std::istringstream strm(test);

    // Read in the data
    std::multimap<int, std::string> strmap;
    int N;
    strm >> N;
    std::string word;
    for (int i = 0; i < N; ++i)
    {
        strm >> word;

        // get the average using std::accumulate and divide by the length of the word
        int avg = std::accumulate(word.begin(), word.end(), 0,
                    [&](int total, char val) { return total + val - 'A' + 1; }) / word.length();

        // insert this value in the map
        strmap.insert({ avg, word });

    }

    // output results 
    for (auto& w : strmap)
        std::cout << w.second << "\n";
}

Выходные данные:

TMHEJLIDEHT
PQUPOGTJETGXDQDEMGPNMJEBI
BKNGFEJZWMJNJLSTUBHCFHXWMYUPZM
CJDFYDMYZVOEW
RRPPNG
COSOPYILSPKNKZSTUZVMEERQDL
KGTGFIFWYTKPWTYQQPGKRRYFXN
TQJZMOLQ
YNWEPZKNBOOXNZVWKIUS
LV

std :: аккумулировать используется для сложения значений для получения среднего значения.

Answer 2

Или просто закажите их в конце (второй массив вам не понадобится):

for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
        int sumA = 0, sumB = 0;
        for (int k = 0; k < words[i].size(); k++)
            sumA += words[i][k] - 'A' + 1;
        for (int k = 0; k < words[j].size(); k++)
            sumA += words[j][k] - 'A' + 1;
        if (sumA / words[i].size() > sumB / words[j].size())
            swap(words[i], words[j]);
    }
}

Как показано выше, лучше использовать вектор для хранения ваших данных.

Answer 3

После прочтения следующего слова используйте сортировку вставки ( wiki ), которая является стабильной

1. чтение слова
2. вычисление значения
3. вставка вправильное место в массиве
4. перейти к 1 до i < N, в противном случае распечатать

Не требуется дополнительная процедура сортировки.

Answer 4

string words[N];
int res[N];

Это не является допустимым C ++, вы не можете определить размер стекового массива, используя переменную времени выполнения, хотя некоторые компиляторы могут поддерживать такую ​​функцию. Вместо этого вы можете использовать, скажем, std::vector, который ведет себя подобно массиву.

vector<string> words;
vector<int> res;

for (int i = 0; i < N; i++) {
    int sum = 0;
    int value = 0;
    int temp = 0;
    string word;
    cin >> word;
    words.push_back(word);
    for (int j = 0; j < word.length(); j++) {
        sum += (int)word[j] - 64;
    }
    value = sum / word.length();
    res.push_back(value);
}

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (res[i] < res[j]) {
            swap(res[i], res[j]);
            swap(words[i], words[j]);
        }
    }
}

---

Порядок следования из-за нестабильности вашего алгоритма сортировки. Стабильный означает, что элементы с одинаковыми значениями будут поддерживать одинаковый порядок относительно друг друга.

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (res[i] < res[j]) {
            swap(res[i], res[j]);
            swap(words[i], words[j]);
        }
    }
}

То, что у вас есть, очень близко к пузырьковой сортировке, которая стабильна.

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N - i - 1; j++) { // i elements sorted so far
        if (res[j] > res[j + 1]) {
            swap(res[j], res[j + 1]);
            swap(words[j], words[j + 1]);
        }
    }
}

C ++также обеспечивает стабильную сортировку в <algorithm>, но она не может функционировать напрямую в двух массивах, как это, к сожалению, один вариант - вычислить значение на лету, другой - создать класс, содержащий оба элемента, и отсортировать его, илидругой для сортировки индексов.

std::stable_sort(words.begin(), words.end(), [&](auto &a, auto &b)
{
    int suma = 0, sumb = 0; // better yet, make a "int value(const string &str)" function.
    for (int j = 0; j < a.length(); j++) {
        suma += (int)a[j] - 64;
    }
    for (int j = 0; j < b.length(); j++) {
        sumb += (int)b[j] - 64;
    }
    int valuea = suma / a.length();
    int valueb = sumb / b.length();
    return valuea < valueb;
});

Класс, содержащий оба элемента, довольно прост, для индексов создайте 3-й массив и отсортируйте его.

vector<size_t> indices;
...
    string word;
    cin >> word;
    indices.push_back(words.size());
    words.push_back(word);
...
std::stable_sort(indices.begin(), indices.end(), [&](auto a, auto b){ return res[a] < res[n]; });
for (int i = 0; i < N; i++) {
    cout << words[indices[i]] << endl;
}

Answer 5

Возможным решением может быть порядок массива результатов во время построения.

Когда вы добавляете слова в массив результатов, используйте полученный результат, чтобы добавить слово в нужном месте. Таким образом, вы можете проверить, существует ли уже такое же значение, и добавить новое слово после предыдущего с тем же значением.