Научимся считать за константу 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. Осталось посчитать для всех и найти наименьший.









Автокомментарий: текст был обновлен пользователем akhan42 (предыдущая версия, новая версия, сравнить).