字符串权重均衡挑战：寻找操作最少的无效字符串

The Problem Recap #

Given N strings (exactly one invalid), each string's weight is the sum of its characters (a=1, ..., z=26). You can increment/decrement any string's weight by 1 any number of times. We need to find which string is the invalid one such that the total number of operations to make all remaining strings have equal weight is minimized.

Why Your Current Code Doesn't Work #

Your current solution picks the string with the smallest weight as the invalid one, which worked for the sample input purely by coincidence. The flaw here is that the string with the smallest (or largest) weight isn't always the one that, when removed, leaves a set of weights where the total adjustment cost is minimized.

For example: Suppose you have weights [50,50,50,40,70]. If you remove the 40, the total cost to adjust the rest to 50 is 20 (70→50). If you remove the 70, the total cost is 10 (40→50). Here, removing the largest weight gives a lower cost, but your code would incorrectly pick the 40.

The key insight here is: To minimize the total number of operations to make a set of numbers equal, you should adjust all numbers to the median of the set (since the median minimizes the sum of absolute deviations).

Correct Step-by-Step Approach #

1. Calculate the weight for each string and store both the string and its weight.
2. For each string in the list:
   • Create a new list of weights excluding this string's weight.
   • Find the median of this new list (this is the target weight we'll adjust all remaining strings to).
   • Compute the total number of operations: sum of absolute differences between each weight in the new list and the median.
3. Select the string that corresponds to the smallest total operation count.

Ruby Code Implementation #

# Build the character weight hash once (outside test cases for efficiency)
char_weights = {}
('a'..'z').each_with_index { |char, idx| char_weights[char] = idx + 1 }

t = gets.to_i
t.times do
  n = gets.to_i
  str_weights = []
  n.times do
    str = gets.chomp
    weight = str.chars.sum { |c| char_weights[c] }
    str_weights << [str, weight]
  end

  min_ops = Float::INFINITY
  invalid_str = ""

  str_weights.each_with_index do |(current_str, _), idx|
    # Get all weights except the current string's weight
    remaining_weights = str_weights.reject.with_index { |_, i| i == idx }.map { |sw| sw[1] }
    # Sort to find the median
    sorted_weights = remaining_weights.sort
    median = sorted_weights[sorted_weights.size / 2]
    # Calculate total operations needed
    total_ops = remaining_weights.sum { |w| (w - median).abs }
    # Update the minimum if this candidate is better
    if total_ops < min_ops
      min_ops = total_ops
      invalid_str = current_str
    end
  end

  puts invalid_str
end

Let's Test This With Your Sample Input #

Sample strings and their weights:

• chakshu: 71
• pekka: 44
• punk: 62
• golem: 52
• tyagi: 62

Let's compute for each candidate:

1. Exclude chakshu: Remaining weights [44,62,52,62]. Sorted: [44,52,62,62]. Median is 62. Total ops = (44-62).abs + (62-62) + (52-62).abs + (62-62) = 18 + 0 +10 +0 = 28.
2. Exclude pekka: Remaining weights [71,62,52,62]. Sorted: [52,62,62,71]. Median is 62. Total ops = (71-62) + (62-62) + (52-62).abs + (62-62) =9 +0 +10 +0=19.
3. Exclude punk: Remaining weights [71,44,52,62]. Sorted: [44,52,62,71]. Median is62. Total ops=9+18+10+0=37.
4. Exclude golem: Remaining weights [71,44,62,62]. Sorted: [44,62,62,71]. Median is62. Total ops=9+18+0+0=27.
5. Exclude tyagi: Same as excluding punk, total ops=37.

The code correctly picks "pekka" as the answer, matching your sample explanation.

Key Notes #

• Using the median is critical here because it minimizes the sum of absolute differences. Using the mean would lead to higher total operations in many cases.
• When the remaining list has an even number of elements, any value between the two middle numbers will give the same total operation count—so picking either middle number works perfectly.

内容的提问来源于stack exchange，提问作者Aniket Tiwari