Матч 381, Наилучшее имя (TheBestName)

Дивизион 2, Уровень 1

Определим функцию сравнения имен. Припишем вес каждой букве: ‘A’ – 1, ‘B’ – 2, …, ‘Z’ – 26. Вес имени равен сумме весов букв, входящих в него. Имя с большим весом более значимо чем имя с меньшим весом. Среди имен с одинаковым весом более значимым является то, которое идет лексикографически раньше. При этом нет лучшего имени чем JOHN, имя JOHN всегда является наиболее значимым.

Отсортировать входной массив имен в порядке убывания их значимости.

Класс: TheBestName

Метод: vector<string> sort(vector<string> names)

Ограничения: names содержит от 1 до 50 строк, names[i] содержит от 1 до 50 заглавных букв латинского алфавита ‘A’ – ‘Z’.

Вход. Массив имен names.

Выход. Массив имен в порядке убывания их значимости.

Пример входа

names

{"JOHN", "PETR", "ACRUSH"}

{"JOHN", "A", "AA", "AAA", "JOHN", "B", "BB", "BBB", "JOHN", "C", "CC", "CCC", "JOHN"}

{"BATMAN", "SUPERMAN", "SPIDERMAN", "TERMINATOR"}

Пример выхода

{"JOHN", "ACRUSH", "PETR"}

{"JOHN","JOHN","JOHN","JOHN","CCC","BBB","CC","BB","AAA","C","AA","B","A"}

{"TERMINATOR", "SUPERMAN", "SPIDERMAN", "BATMAN"}

РЕШЕНИЕ

сортировка

Задача сводится к написанию функции сортировки строк f согласно заданным условиям. Строки a и b меняются местами при вызове f(a, b), если функция f возвращает ложь. Значимость имени JOHN отобразим следующим фактом: если a = JOHN, то вернем 1 (переставлять a и b не надо), если b = JOHN, то вернем 0 (a и b следует переставить).

Функция sum вычисляет вес имени. Если имя a имеет больший вес, чем b, то возвращаем 1 (a и b не переставляем). В случае равенства весов лексикографически сравниваем строки, возвращая значение a < b. В остальных случаях функция f возвращает 0.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int sum(string s)

{

int i,res;

for(res=i=0;i<s.size();i++)

res += (s[i] - 'A' + 1);

return res;

}

// true, not to swap

int f(string a, string b)

{

if (a == "JOHN") return 1;

if (b == "JOHN") return 0;

if (sum(a) > sum(b)) return 1;

if (sum(a) == sum(b)) return a < b;

return 0;

}

class TheBestName

{

public:

vector<string> sort(vector<string> names)

{

std::sort(names.begin(),names.end(),f);

return names;

}

};