Научимся считать за константу opportunity cost для каждого tuple `(x, y, z)`.↵
↵
Opportunity cost для `(x, y, z)` равен `max по i=1...n величины max(x[i] - x, 0) + max(y[i] - y, 0) + max(z[i] - z, 0)`.↵
↵
Покажем что не нужно пробегать все `i`, а только следующий индексы:↵
↵
Пусть индексы `m1, m2, m3, m4, m5, m6, m7` такие что↵
↵
`m1` максимизирует `x[m]`↵
↵
`m2` максимизирует `y[m]`↵
↵
`m3` максимизирует `z[m]`↵
↵
`m4` максимизирует `x[m] + y[m]`↵
↵
`m5` максимизирует `y[m] + z[m]`↵
↵
`m6` максимизирует `x[m] + z[m]`↵
↵
`m7` максимизирует `x[m] + y[m] + z[m]`.↵
↵
То есть например, `y[m5] + z[m5]` максимален среди `y[i] + z[i]` для любых `i`.↵
↵
Докажем что максимум opportunity cost для произвольного `(x, y, z)` достигается на одном из `m1, m2, m3, m4, m5, m6, m7`.↵
Пусть он достигся на `i` вот собственно он `OC[i] = max(x[i] - x, 0) + max(y[i] - y, 0) + max(z[i] - z, 0)`,↵
к примеру, пусть первый максимум при этом был нулем, второй и третий не нулевыми (остальные случаи аналогичны). Тогда↵
`OC[i] = 0 + (y[i] - y) + (z[i] - z) = y[i] + z[i] - y - z <= y[m5] + z[m5] - y - z = 0 + (y[m5] - y) + (z[m5] - z) <= max(x[m5] - x, 0) + max(y[m5] - y, 0) + max(z[m5] - z, 0) = OC[m5]`. ↵
↵
Последнее неравенство в силу `a <= max(a, b) и b <= max(a, b)`.↵
То есть получили что на `m5` opportunity cost не меньше, а значит и максимизирующий `i` это `m5`.↵
↵
То есть для каждого `(x, y, z)` если считаем за константу opporunity cost. Осталось посчитать для всех и найти наименьший.
↵
Opportunity cost для `(x, y, z)` равен `max по i=1...n величины max(x[i] - x, 0) + max(y[i] - y, 0) + max(z[i] - z, 0)`.↵
↵
Покажем что не нужно пробегать все `i`, а только следующий индексы:↵
↵
Пусть индексы `m1, m2, m3, m4, m5, m6, m7` такие что↵
↵
`m1` максимизирует `x[m]`↵
↵
`m2` максимизирует `y[m]`↵
↵
`m3` максимизирует `z[m]`↵
↵
`m4` максимизирует `x[m] + y[m]`↵
↵
`m5` максимизирует `y[m] + z[m]`↵
↵
`m6` максимизирует `x[m] + z[m]`↵
↵
`m7` максимизирует `x[m] + y[m] + z[m]`.↵
↵
То есть например, `y[m5] + z[m5]` максимален среди `y[i] + z[i]` для любых `i`.↵
↵
Докажем что максимум opportunity cost для произвольного `(x, y, z)` достигается на одном из `m1, m2, m3, m4, m5, m6, m7`.↵
Пусть он достигся на `i` вот собственно он `OC[i] = max(x[i] - x, 0) + max(y[i] - y, 0) + max(z[i] - z, 0)`,↵
к примеру, пусть первый максимум при этом был нулем, второй и третий не нулевыми (остальные случаи аналогичны). Тогда↵
`OC[i] = 0 + (y[i] - y) + (z[i] - z) = y[i] + z[i] - y - z <= y[m5] + z[m5] - y - z = 0 + (y[m5] - y) + (z[m5] - z) <= max(x[m5] - x, 0) + max(y[m5] - y, 0) + max(z[m5] - z, 0) = OC[m5]`. ↵
↵
Последнее неравенство в силу `a <= max(a, b) и b <= max(a, b)`.↵
То есть получили что на `m5` opportunity cost не меньше, а значит и максимизирующий `i` это `m5`.↵
↵
То есть для каждого `(x, y, z)` если считаем за константу opporunity cost. Осталось посчитать для всех и найти наименьший.
