Правильный ли алгоритм?

Question

[Paul Fawkes]

Вот формулировка задачки, ограничение на время 5с, на память 256мб, тесты на правильность мой алгоритм не прошёл не могу понять почему, можете помочь разобраться почему, или же посоветовать алгоритм лучше

using System;
using System.Linq;

namespace Testing
{
    class Program
    {
        static void Main(string[] args)
        {
            int numberOfTasks = Convert.ToInt32(Console.ReadLine());
            int numberOfTestDevice = Convert.ToInt32(Console.ReadLine());
            int[] testTime = new int[numberOfTasks];

            for (int i = 0; i < numberOfTasks; i++)
            {
                testTime[i] = Convert.ToInt32(Console.ReadLine());
            }

            testTime = SortArray(testTime);
            int totalTime = 0;
            int x= 0;

            for (int i = 1; i <= testTime.Length; i++)
            {
                totalTime += ((x * 2) + 1) * testTime[i - 1];

                if (i % numberOfTestDevice == 0)
                    x++;
            }

            Console.WriteLine(totalTime);
        }

        static int[] SortArray(int[] inputArray)
        {
            int[] countArray = new int[inputArray.Max() + 1];
            for (int i = 0; i < inputArray.Length; i++)
            {
                countArray[inputArray[i]]++;
            }
            int[] sortedArray = new int[inputArray.Length];
            int sortedArrayIndex = 0;
            for (int i = countArray.Length-1; i >=0; i--)
            {
                for (int j = 0; j < countArray[i]; j++)
                {
                    sortedArray[sortedArrayIndex++] = i;
                }
            }
            return sortedArray;
        }
    }
}

Comments

[#]

ересь твой предыдцщий вопрос. продолжай хамить отвечающим. тебе уже дважды указади на верный путь.. хотя.. может не везде точно.. )) .. но свой ответ с каментами я удалил, после прямого оскорбления. ищи теперь сам, умник. успехов

[#]

и если ты советов по дотнету не понимаешь.. ну конечно... отвечающий виноват ))

Answer 1

[Rsa97]

Судя по примеру, задачи должны выполняться последовательно, но каждая следующая может быть запущена на произвольном устройстве.
Значит сортируем задачи по времени в убывающем порядке и запускаем на устройствах по кругу.

function allTestsTime(numDevices, testTimes) {
  testTimes.sort((a, b) => b - a);
  let totalTime = 0;
  for (let i = 0; i < testTimes.length; i++) {
    totalTime += testTimes[i] * (2 * Math.floor(i / numDevices) + 1);
  }
  return totalTime;
}

console.log(allTestsTime(3, [6, 2, 5]));

// 13

Comments

[Paul Fawkes]

Ну я же так и сделал, это не правильно

[Rsa97]

Paul Fawkes, А больше тестовых данных нет?

[Paul Fawkes]

3задачи 2 устройства и время 6, 5, 2 ответ 17, решение 1 и последнюю задачу тестируем на первом устройстве вторую задачу на втором

[Rsa97]

Paul Fawkes, Тогда, вроде, всё правильно. У меня получилось 17. Самые длинные задачи тестируем первыми, получаем время 6*(2*0+1) = 6 и 5*(2*0+1) = 5, оставшуюся задачу тестируем на любом устройстве, 2*(2*1+1) = 6. 6+5+6 = 17.

[Paul Fawkes]

Rsa97, да, но у меня не засчитывают это задание, ибо ошибка, может не в алгоритме, а самом Коде

[Rsa97]

Paul Fawkes, На первый взгляд, ошибок нет. Надо отлаживать, либо трассировать в отладчике, либо выводить промежуточные значения, смотреть как и что считает.

[Paul Fawkes]

Rsa97, дело наверное в сортировке, если простой кастомной сортировкой подсчета то ошибка на 8 тесте, а если linq то на 6 в чем бы могло быть дело

[Wataru]

Очень похоже на переполнение. Попробуйте тест, где одно устройство и миллион задач по 100 каждая.

Answer 2

[Wataru]

Очень похоже на переполнение. Попробуйте тест, где одно устройство и миллион задач по 100 каждая.