Где ошибка в доказательстве?

Question

[watermelon11]

Вот

def find_min_time(tests):
    results = []
    for _ in range(tests):
        n = int(input())
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
 
        tasks = []
        total_b = 0
 
        for i in range(n):
            task = (a[i], b[i])
            tasks.append(task)
            total_b += task[1]
 
        tasks = sorted(tasks, key=lambda task: task[0])
 
        subordinate_min = 0
        boss_b = total_b
 
        for task in tasks:
            if boss_b > task[0]:
                boss_b -= task[1]
                subordinate_min = task[0]
 
        results.append(max(subordinate_min, boss_b))
 
    return results
 
tests = int(input())
results = find_min_time(tests)
 
for result in results:
    print(result)

Вот условие:ограничение по памяти на тест256 MB
В IT-отдел поступило n поручений, каждое из которых должно быть выполнено.

Для каждого поручения (обозначим его номер за i) у начальника отдела есть два варианта, что делать с ним:

назначить его одному из своих подчиненных, тогда поручение будет выполнено за ai минут;
выполнить его самостоятельно за bi минут.
Можно считать, что количество подчиненных достаточно, чтобы никто не получил более одного поручения — поэтому подчиненные будут работать над поручениями параллельно. Однако те поручения, которые начальник оставит себе, он будет выполнять последовательно.
Опираясь на данный код и на данное условие,докажи,что сортировка в данном случае по времени подчиненных даст наилучшее решение
Вот доказательство:Шаг 1: База индукции
Для n=1: имеется одна задача
(a[1],b[1]).
* Если задачу выполняет подчиненный, общее время выполнения равно 
Tmax =a[1].
* Если задачу выполняет начальник, общее время выполнения равно
Tmax =b[1].
Максимальное время выполнения равно:
Tmax =max(a[1],b[1]).
Для n=1 сортировка по
a[i] бессмысленна (один элемент). Таким образом, утверждение выполняется.

Шаг 2: Индуктивное предположение
Предположим, что для
n=k задач сортировка по возрастанию
a[i] минимизирует Tmax .
То есть, если задачи упорядочены как:
a[1]≤a[2]≤⋯≤a[k],
то оптимальное распределение задач между начальником и подчиненными минимизирует Tmax .
Шаг 3: Индуктивный переход (для n=k+1)
Добавим новую задачу
(a[k+1],b[k+1]) к уже отсортированным задачам:
(a[1],b[1]),(a[2],b[2]),…,(a[k],b[k]),(a[k+1],b[k+1]),где
a[1]≤a[2]≤⋯≤a[k+1].
Теперь нам нужно распределить задачу
(a[k+1],b[k+1]), чтобы минимизировать:
Tmax =max(subordinate_time,boss_time),
где:
subordinate_time — максимальное время задач, переданных подчиненным.
boss_time — суммарное время задач, оставшихся начальнику.

Сравнение двух вариантов
1. Если задачу (a[k+1],b[k+1]) выполняет подчиненный:

subordinate_time обновляется как max
max(a[1],a[2],…,a[k+1])=a[k+1].

boss_time не изменяется и равно 
∑b[i] для всех остальных задач.
1. Если задачу (a[k+1],b[k+1]) выполняет начальник:
subordinate_time остается равным
max(a[1],a[2],…,a[k])=a[k].

boss_time обновляется как ∑b[i]+b[k+1].

Comments

[Akina]

В условии почему-то не определено, что такое "наилучшее решение". Нет критериев ни того, по какому критерию следует сформировать план выполнения задач (вовсе не факт, что таковое - решение с минимальным временем), ни того, как следует оптимизировать алгоритм, что считать его оптимумом.

Более того, даже просто разбор шага 1 показывает, что наилучшим планом выполнения почему-то является решение с максимальным временем... Но это бессмысленно. К тому же, при таком определении решение тривиально - если существует задание, время выполнения которого подчинённым больше, чем время выполнения начальником всех задач, то наиболее длительное задание и есть решение, иначе решением является выполнение всех задач начальником.

[watermelon11]

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

Answer 1

[Wataru]

Доказательство не верно из-за индуктивного перехода. Вы рассматриваете только уже отсортированные наборы задач. Не ясно, что добавляя задачи в другом порядке вы получаете варианты не лучше. Вы так же не показали, что вот эти 2 варианта дают оптимальное время для k+1 задачи.

Правильное доказательство весьма простое и без индукции. Общее время будет

Max(sum{i-начальнику}(bi), max{i - подчиненным}(ai))

.
Отсюда видно, что если вы какую-то задачу дали подчиненному, то все задачи с меньшим A нет смысла давать начальнику. Ведь второе слагаемое-максимум от этого не изменится, но первое увеличится. Можно "бесплатно" выполнить эти задачи подчиненными. Поэтому в оптимальном ответе вы даете какое-то множетсво минимальных A подчиненым, а остальные начальнику. Иначе можно какие-то задачи перекинуть с начальника на подчиненного и уменьшить первое слагаемое не меняя второе, уменьшив таким образом ответ, т.е. в этом случае решение точно не оптимальное.
Чтобы все варианты возможных оптимумов перебрать надо отсортировать задачи по возрастанию A. Это код и делает. поддерживается сумма B у всех оставшихся задач, а от текущей берется A - который и будет максимумом для всех задач с меньшим A.