Вам дано N строк, и одна из них недействительна. Каждая строка имеет вес, равный сумме весов ее символов. Вес символов представлен следующим образом
вес а равен 1 вес b равен 2 вес c равен 3
и так далее
Вы можете выполнить следующую операцию над строкой
Ваша цель — уравнять веса всех строк, кроме одной (мы называем ее недопустимой строкой), выполняя эти операции любое количество раз. Найдите неверную строку, т.е. приравняйте всю строку, кроме недопустимой строки, к некоторому весу W, такому, чтобы количество требуемых операций было минимальным.
Примечание
Строка содержит только буквы нижнего регистра Есть только одна неверная строка
Пример у нас есть 5 строк
чакшу пекка панк голем тяги
выход
пекка
Объяснение
Вес струнной чакшу равен 3 + 8 + 1 + 11 + 18 + 8 + 20 = 71. Точно так же для пекки, панка, голема и тяги это 44, 62, 52 и 62 соответственно.
Теперь считайте чакшу недопустимой строкой, операций, необходимых для выравнивания остальных, 28. если pekka недействителен, требуется 19 операций если панк недействителен, нам нужно 37 ходов, чтобы сравнять Аналогично для голема и тяги нужно 27 и 37 операций Таким образом, pekka - недопустимая строка, так как для ее удаления требуется наименьшее количество ходов.
Что я пробовал до сих пор
t = gets.to_i
hsh = {}
('a'..'z').each_with_index{|elem, index| hsh[elem] = index + 1}
while t > 0 do
n = gets.to_i
result = {}
while n > 0 do
str = gets.chomp
result[str] = str.chars.map{|d| hsh[d]}.sum
n -= 1
end
puts [result.min_by{|k, v| v}].first.first
t -= 1
end
Но это решение проходит только тестовый пример. Когда я запускаю все тестовые примеры, это дает мне неправильный ответ.
Я полагаю, вы имеете в виду: «Теперь считайте чакшу недопустимой строкой, операции, необходимые для выравнивания остальных, равны 28. Если pekka недействительна ...», а не «... 28, если pekka недействительна ....».
Минимальные шаги, чтобы сделать вес всех строк равным, будут состоять в том, чтобы сделать строки равными медиане строк. Недопустимой строкой будет строка, которая уменьшает общее количество шагов на максимальную величину.
Итак, для вычисления медианы мы вычисляем веса каждой строки и сортируем их, чтобы найти медиану. Затем мы вычисляем индекс строки, которая принимает максимальное число. шаги, чтобы добраться от медианы и вернуть его в качестве ответа.
Проблема в приведенном выше алгоритме возникает, когда длина списка строк четная. Поэтому нам также необходимо рассчитать общее число. предпринятых шагов (исключая шаги, предпринятые недопустимой строкой) для достижения медианы. Таким образом, ответ из двух строк соответствует минимальному нету. Всего шагов.
Это код Python для вышеуказанного алгоритма. Я сильно прокомментировал, если вы ничего не понимаете, просто спросите в разделе комментариев.
def get_weight(char): ### gets ascii value of character then
return ord(char)-ord('a')+1 ### subtract ascii of 'a' to get weight
def get_max_steps(weights,length,median):
max_steps=-1
max_indx=-1
total_steps=0
for indx in range(length): ### for each word
tmp_steps=abs(weights[indx]-median) ### calculate steps req to reach
total_steps+=tmp_steps ### median weight
if max_steps<tmp_steps:
max_steps=tmp_steps ### store the max steps required in max_steps
max_indx=indx ### and index for which its required in max_indx
return total_steps-max_steps,max_indx ### exclude the max_steps from total steps for the invalid string
def function(words,length):
weights=[0 for i in range(length)] ### array to store weights of each word
for indx in range(length): ### for each word
weight=0 ###
for char in words[indx]: ### calculate weight of each word
weight+=get_weight(char) ###
weights[indx]=weight ### store it in the array
sorted_weights=sorted(weights) ### sort the array
median=sorted_weights[length/2] ### get median do Integer divison
total_steps,max_indx=get_max_steps(weights,length,median) ### calculate the total steps required to
### reach median of weight excluding the steps for invalid string at max_ind
if length%2==0: ### if array's length is even
median=sorted_weights[length/2 -1] ### get second median and do similar step as above and do Integer division here
ntotal_steps,nmax_indx=get_max_steps(weights,length,median)
if ntotal_steps<total_steps: ### if the total steps using second median is less
max_indx=nmax_indx ### then the string by this median is appropriate choice for invalid string
return words[max_indx] ### return invalid string
tests=int(input()) ### taking no. of test cases as input
for i in range(tests): ### run for-loop for tests no. of times
length=int(input()) ### taking array's length and array of strings
words=input().split() ### as input
print(function(words,length)) ### printing the functions result
Какова будет временная и пространственная сложность?
это будет зависеть от суммы длин слов в массиве слов. Пусть эта сумма будет m
. И длина массива слов будет n
. Тогда временная сложность равна O(m+ nlogn)
.
Начнем с создания метода, вычисляющего вес каждой строки.
def weight(s)
base = 'a'.ord - 1
s.each_char.sum { |c| c.ord - base }
end
или
def weight(s)
s.each_char.sum(&:ord) - s.size * ('a'.ord - 1)
end
Например,
arr = ["chakshu", "pekka", "punk", "golem", "tyagi"]
weights = arr.map { |s| weight(s) }
#=> [71, 44, 62, 52, 62]
Затем создайте метод, определяющий минимальное количество итераций, необходимых для выравнивания весов всех строк, кроме одной. Предположим, уравненный вес равен x
. Легко показать, что значение x
, минимизирующее сумму абсолютных отклонений от x
, равно медиане весов.
def steps_required(wts)
median = wts.sort[(wts.size+1)/2]
wts.sum { |w| (w - median).abs }
end
Например,
steps_required(weights.values_at(1,2,3,4)) #=> 28
steps_required(weights.values_at(0,2,3,4)) #=> 19
steps_required(weights.values_at(0,1,3,4)) #=> 37
steps_required(weights.values_at(0,1,2,3)) #=> 37
Теперь нам нужно только объединить все это в метод, который вызывает методы weight
и steps_required
, которые я создал выше.
def find_invalid_str(arr)
weights = arr.map { |s| weight(s) }
all_indices = (0..arr.size-1).to_a
i = arr.each_index.min_by do |i|
steps_required(weights.values_at(*(all_indices-[i])))
end
arr[i]
end
find_invalid_str(arr)
#=> "pekka"
Какова будет временная сложность этого?
@AniketTiwari, сейчас речь идет о O ((n ^ 2) log (n)), где n = arr.size
, но завтра я сделаю редактирование, которое сделает O (n log (n)). Спасибо за вопрос.
Я буду ждать решения n(log(n))
Дайте определение «неправильно» в конкретных технических терминах, чтобы мы знали, где помочь.