Найти максимальную разность между конечной и начальной суммой

Question

Подскажите как решить задачу из Тинькофф.Контест

У Кости есть бумажка, на которой написано n чисел. Также у него есть возможность не больше, чем k раз, взять любое число с бумажки, после чего закрасить одну из старых цифр, а на ее месте написать новую произвольную цифру.

На какое максимальное значение Костя сможет увеличить сумму всех чисел на листочке?

Формат входных данных

В первой строке входного файла даны два целых числа n,k — количество чисел на бумажке и ограничение на число операций.

(1≤n≤1000,1≤k≤10) Во второй строке записано n чисел a — числа на бумажке (1≤a≤10)

Формат выходных данных

В выходной файл выведите одно число — максимальную разность между конечной и начальной суммой.

Замечание

В первом примере Костя может изменить две единицы на две девятки, в результате чего сумма чисел увеличится на 16.

Во втором примере Костя меняет число 85 на 95.

В третьем примере можно ничего не менять.

Обратите внимание, что ответ может превышать вместимость 32-битного типа данных.

Я попытался решить задачу разными способами, но в итоге зашел в тупик:

import (
 "fmt"
 "strconv"
 "math"
)

func main() {
//  k := 1
  numbers := []int{99, 5, 85}
  var res []int

  for _, number := range numbers {
    for i:=0; i < len(strconv.Itoa(number)); i++ {
      str := strconv.Itoa(number)[i]
      digit, err := strconv.Atoi(string(str))
      if err != nil {
        fmt.Println(err)
      }
     operation := int(math.Pow(10, float64(i))*(float64(9-digit)))
      res = append(res, operation)
    }
  }
    fmt.Println(res)
}

Подскажите как можно решить данную задачу

Answer 1

Ваша задача - для каждой цифры посчитать, на сколько увеличит сумму её изменение на девятку (какую выгоду она даёт). После этого взять k лучших выгод и сложить их. Для хранения выгод можно использовать очередь по приоритетам на k элементов.

Например, для чисел 7132 89091 при k=4

 7     1    3   2          8      9      0     9   1
 2000  800  60  7          10000  0      900   0   8
 сумма 4 лучших:
 10000+2000+900+800 =13700

(Очередь по приоритетам может быть на основе бинарной кучи, может, в го есть готовая, но для k<=10 в принципе можно и простыми средствами обойтись вроде сортированного массива с вытеснением наименьшего, или вообще хранить всё, а потом отсортировать)

Да, ещё избавьтесь от такого: math.Pow(10, float64(i)). Вес разряда можно в целых числах на ходу считать, если вы идёте от правой цифры числа, примерно так в псевдокоде:

t = value
wt = 1
while t > 0:
   digit = t%10
   gain = (9 - digit) * wt
   //gain занести, куда нужно
   wt *= 10
   t //= 10     //целочисленно

Answer 2

на основе элегантной идеи @MBo реализовал на Java эту задачку, возможно кому-то будет полезно. Для хранения выгод использовал обычный ArrayList() с обратной сортировкой и суммированием первых k результатов, потому что стандартная библиотечная PriorityQueue не поддерживает фиксированный размер и пришлось бы немного танцевать с бубнами или привлекать другие библиотеки (или есть другие решения, а я не нашел). В любом случае, за условные ограничения памяти не вышло, но при больших значениях n и t может потребоваться оптимизация. Может кому-то будет полезно.

Scanner scanner = new Scanner(System.in);

        int n, k = 0;
        
        long sum = 0;
        
        List<Long> values = new ArrayList<>(); 

        while (scanner.hasNext()) {

            n = scanner.nextInt();
            k = scanner.nextInt();
   
            for (int i = 0; i < n; i++) {

                int t = scanner.nextInt();
                int weight = 1;
                while (t > 0) {
                    int digit = t % 10;
                    long gain = (9 - digit) * weight;
                    values.add(gain);
                    weight *= 10;
                    t /= 10;
                }
            }
            sum = values.stream()
                .sorted(Comparator.reverseOrder())
                .limit(k)
                .reduce(0l, Long::sum);
        }
        System.out.println(sum);
    }

Answer 3

Моё решение на Java, синтаксис можно опустить а смотреть на алгоритм. решение предоставаленное другими пользователями StackOverFlow кажется немного замудренными, возможно алгоритмическая сложность у них более низкая, думаю мой ответ не будет лишним.

    import java.util.Scanner;

public class fourthTask {
    public static long changeDigitSum(long number) {
        long divisor = 1;
        while (divisor <= number) {
            divisor *= 10;
        }
        divisor /= 10;
        while (divisor > 0){
            if ((((number / divisor) % 10 ) != 9))
                return (9 - ( (number / divisor) % 10 )) * divisor;
            divisor /= 10;
        }
        return 0;
    }

    public static long changeNumber(long[] arr){
        int maxIndex = 0; // n <= 1000
        long max = 0; // max <= 9e10
        for (int i = 0; i < arr.length; i++) {
            long tmp = changeDigitSum(arr[i]); // tmp <= 9e10
            if (tmp > max ){
                max = tmp;
                maxIndex = i;
            }

        }
        arr[maxIndex] += max;
        return max;
    }

    public static void main(String[] args){
        //  taking input

        Scanner sc = new Scanner(System.in);
        long sumDifference = 0;
        int n = sc.nextInt();  // n <= 1000
        int k = sc.nextInt(); // k <= 1e5
        long[] mas = new long[n];
        for ( int i = 0; i < n; i++ )
            mas[i] = sc.nextInt(); // input <= 1e10

        // processing

        for (int i = 0; i < k; i++) { // k times
            sumDifference += changeNumber(mas);

        }
        System.out.println(sumDifference);

    }
}

БЛОГ НА HUSL

Найти максимальную разность между конечной и начальной суммой

Ответы (3 шт):