Матч 341, Изменение строки (ChangingString)

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

Имеются две строки a и b одинаковой длины, содержащих латинские буквы ‘a’-‘z’. Расстоянием между буквами называется модуль разности их ASCII кодов. Расстоянием между строками a и b называется сумма расстояний между буквами, стоящих в одних и тех же позициях. Например, расстояние между "abcd" и "bcda" равно 6 (1 + 1 + 1 + 3).

В строке a следует изменить в точности k букв. Найти наименьшее возможное расстояние между строками a и b после такого изменения.

Класс: ChangingString

Метод: int distance(string a, string b, int k)

Ограничения: строки a и b имеют одинаковую длину и содержат от 1 до 50 символов ‘a’-‘z’, 1 £ k £ a.size().

Вход. Строки a и b, число k.

Выход. Наименьшее возможное расстояние между строками a и b после изменения k символов строки a.

Пример входа

a	b	k
“ab”	“ba”	2
“aa”	“aa”	2
“aaa”	“baz”	1

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

0

2

1

РЕШЕНИЕ

сортировка + жадный алгоритм

Очевидно, что изменять следует буквы строки a в тех позициях, в которых расстояния между буквами наибольшие. Вычислим в массиве d расстояния между буквами и отсортируем их по возрастанию. Пусть длина входных строк равна n. Тогда расстояния, хранящиеся в ячейках от d[0] до d[n – k – 1], будут включены в результирующее расстояние между строками a и b.

Пусть в некоторой позиции i следует менять букву. Если a[i] = b[i], то букву в позиции i следует изменить на следующую (или предыдущую), таким образом сделав расстояние между буквами равным 1. Если a[i] ¹ b[i], то букву a[i] следует заменить на b[i]. Просматриваем значения ячеек от d[n – k] до d[n – 1]. Если значение ячейки равно 0, то буквы в соответствующих позициях были равными, и к результату следует прибавить 1. Иначе прибавляем 0.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#include <algorithm>

#include <numeric>

using namespace std;

vector<int> d;

class ChangingString

{

public:

int distance(string a, string b, int k)

{

int i, res;

for(i = 0; i < a.size(); i++) d.push_back(abs(a[i] - b[i]));

sort(d.begin(),d.end());

res = accumulate(d.begin(),d.end()-k,0);

for(i = a.size() - k; i < a.size(); i++)

res += (d[i] ? 0 : 1);

return res;

}

};