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

@Lezvie · Регистрация: 31.01.2014

Author24 — интернет-сервис помощи студентам

Пожалуйста помогите с задачей
Мальчик Антон решает вступительную работу в летний математический лагерь. В ней N заданий, которые можно выполнять в произвольном порядке. Разные задачи требуют разного времени для решения. При этом известно, что если задание с номером i выполнять j-м по счету, Антону потребуется Ti*j времени: чем больше думаешь, тем больше устаешь. Например, если начать с первой задачи, а затем выполнить вторую, то потребуется T1*1 + T2*2 времени, а если выполнить сначала вторую задачу, а затем первую – то T2*1 + T1*2. Подскажите Антону, в каком порядке нужно решать задачи, чтобы на выполнение всей работы ушло как можно меньше времени.

Входные данные
В первой строке вводится число N, во второй строке —N чисел через пробелT1, T2, …, TN, разделенные пробелами. Все числа целые и удовлетворяют следующим ограничениям: 0 < N ≤ 10, 0 < Ti ≤ 100.

Выходные данные
Требуется вывести сначала минимальное время, за которое можно решить все задачи, а затем – номера задач в том порядке, в котором их нужно решать, чтобы уложиться в это время. Все числа разделяются пробелами. Если решений несколько, нужно выдать любое из них.

Пример:
Ввод:2 2 3
Вывод:7 2 1

valeriikozlov · 01.02.2014, 07:49

жадный алгоритм:

Pascal    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
uses crt;
const nmax=10;
var a,b:array[1..nmax] of integer;
    i,j,n,t,imax:integer;
begin
  read(n);
  for i:=1 to n do
  read(a[i]);
  for i:=1 to n do begin
  imax:=1;
  for j:=1 to n do 
  if a[imax]<a[j] then imax:=j;  
  t:=t+a[imax]*i;
  b[i]:=imax;
  a[imax]:=0;
  end;
  write(t);
  for i:=1 to n do
  write(' ',b[i]);
  writeln
end.

Новые блоги и статьи Все статьи Все блоги /
JWT аутентификация в Java Javaican 21.04.2025 JWT (JSON Web Token) представляет собой открытый стандарт (RFC 7519), который определяет компактный и самодостаточный способ передачи информации между сторонами в виде JSON-объекта. Эта информация. . .	Спринты Agile: Планирование, выполнение, ревью и ретроспектива EggHead 21.04.2025 Спринты — сердцевина Agile-методологии, позволяющая командам создавать работающий продукт итерационно, с постоянной проверкой гипотез и адаптацией к изменениям. В основе концепции спринтов лежит. . .	Очередные открытия мега простых чисел, сделанные добровольцами с помощью домашних компьютеров Programma_Boinc 21.04.2025 Очередные открытия мега простых чисел, сделанные добровольцами с помощью домашних компьютеров. 3 марта 2025 года, в результате обобщенного поиска простых чисел Ферма в PrimeGrid был найден. . .	Система статов в Unity GameUnited 20.04.2025 Статы — фундаментальный элемент игрового дизайна, который определяет характеристики персонажей, предметов и других объектов в игровом мире. Будь то показатель силы в RPG, скорость передвижения в. . .	Статические свойства и методы в TypeScript run.dev 20.04.2025 TypeScript прочно занял своё место в системе современной веб-разработки. Этот строго типизированный язык программирования не просто расширяет возможности JavaScript — он делает разработку более. . .
Batch Transform и Batch Gizmo Drawing API в Unity GameUnited 20.04.2025 В мире разработки игр и приложений на Unity производительность всегда была критическим фактором успеха. Создатели игр постоянно балансируют между визуальной привлекательностью и плавностью работы. . .	Звук в Unity: Рандомизация с Audio Random Container GameUnited 20.04.2025 В современных играх звуковое оформление часто становится элементом, который либо полностью погружает игрока в виртуальный мир, либо разрушает атмосферу за считанные минуты. Представьте: вы исследуете. . .	Максимальная производительность C#: Советы, тестирование и заключение stackOverflow 20.04.2025 Погружение в мир микрооптимизаций C# открывает перед разработчиком целый арсенал мощных техник. Но как определить, где и когда их применять? Ответ начинается с точных измерений и профилирования. . . .	Максимальная производительность C#: Предсказание ветвлений stackOverflow 20.04.2025 Третий ключевой аспект низкоуровневой оптимизации — предсказание ветвлений. Эта тема менее известна среди разработчиков, но её влияние на производительность может быть колоссальным. Чтобы понять. . .	Максимальная производительность C#: Векторизация (SIMD) stackOverflow 20.04.2025 Помимо работы с кэшем, другим ключевым аспектом низкоуровневой оптимизации является векторизация вычислений. SIMD (Single Instruction, Multiple Data) позволяет обрабатывать несколько элементов данных. . .

@Lezvie 0 / 0 / 0 Регистрация: 31.01.2014 Сообщений: 4

	Антон решает задачи. Подскажите Антону, в каком порядке нужно решать задачи, чтобы на выполнение всей работы ушло как можно меньше времени 31.01.2014, 18:01. Показов 4654. Ответов 1 Метки нет (Все метки) Пожалуйста помогите с задачей Мальчик Антон решает вступительную работу в летний математический лагерь. В ней N заданий, которые можно выполнять в произвольном порядке. Разные задачи требуют разного времени для решения. При этом известно, что если задание с номером i выполнять j-м по счету, Антону потребуется Tij времени: чем больше думаешь, тем больше устаешь. Например, если начать с первой задачи, а затем выполнить вторую, то потребуется T11 + T22 времени, а если выполнить сначала вторую задачу, а затем первую – то T21 + T12. Подскажите Антону, в каком порядке нужно решать задачи, чтобы на выполнение всей работы ушло как можно меньше времени. Входные данные* В первой строке вводится число N, во второй строке —N чисел через пробелT1, T2, …, TN, разделенные пробелами. Все числа целые и удовлетворяют следующим ограничениям: 0 < N ≤ 10, 0 < Ti ≤ 100. Выходные данные Требуется вывести сначала минимальное время, за которое можно решить все задачи, а затем – номера задач в том порядке, в котором их нужно решать, чтобы уложиться в это время. Все числа разделяются пробелами. Если решений несколько, нужно выдать любое из них. Пример: Ввод:2 2 3 Вывод:7 2 1 0

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

Решение