Огромное спасибо natalia за основную идею. Кажется, понял. Но, поскольку ответ явно был не совсем точен в подробностях, на что уже обращено внимание в http://www.codeforces.ru/blog/entry/3557#comment-71902, хочу изложить подробно, как я понял и доделал.

(Многа букф, конечно, но как изложить короче пока не знаю...)

Действовать надо, в зависимости от ситуации, по одной из двух жадных стратегий.

Ситуация А -- количество бутылочек некоторого вида больше-ИЛИ-РАВНО суммарного количества бутылочек всех остальных видов. Стратегия для этого случая -- сливать бутылочки этого максимального по количеству вида со всеми остальными, в порядке возрастания номеров видов. Начав действовать по данной стратегии, так до конца и действуем только по ней.

Ситуация Б -- всё, что не ситуация А. Для этого случая, брать пару видов с наименьшими возможными номерами (изначально -- 1 и 2, в дальнейшем -- первые ненулевые i и j, иначе говоря такие i и j, что \forall k (k<i -> a[k]=0), \forall k (k<j and k!=i -> a[k]=0), где "\forall" -- квантор всеобщности, "->" -- импликация. Сколько штук слить этих двух видов i и j, определяется минимумом из ТРЁХ величин: либо a[i] либо a[j] либо столько, после скольки ситуация превращается из Б в А.

Если произошёл третий из этих вариантов, далее действуем по стратегии ситуации А. В остальных случаях действуем дальше по стратегии ситуации Б, переопределяя i и/или j.

Теперь подробности на тему "как эффективно поддерживать проверку, что ситуация превращается из Б в А". Прочитав входные данные в массив a, пройдём по нему от конца к началу, считая для каждого эл-та сумму от него до конца a[k]+...+a[n]. Все те k, для которых a[k]>a[k+1]+...+a[n], запоминаем -- только они и будут потенциальными кандидатами на роль тех, из-за которых может понадобиться переключиться со стратегии ситуации Б на стратегию ситуации А. Более того, в каждый момент это может быть только самый левый из всех запомненных потенциальных кандидатов (или срабатывает именно он, или не срабатывает никто). Поддерживать кол-во всех ещё не использованных бутылочек -- элементарно. Пусть кол-во всех ещё не использованных бутылочек равно T, текущим самым левым потенциальным кандидатом является номер p (i<j<p). Найдём то количество x сливаний бутылочек видов i и j, при котором ситуация Б превращается в ситуацию А (если это вообще возможно). Это будет минимальное x при котором  T - 2*x - a[p] <= a[p] что равносильно 2*x >= T - 2*a[p], то бишь x = (T - 2*a[p] + 1) div 2. Значит, если (T - 2*a[p] + 1) div 2 <= min(a[i], a[j]), то надо смешать именно столько штук бутылочек видов i и j, а далее действовать по стратегии ситуации А. Иначе, уменьшаем каждый из эл-тов a[i] и a[j] на min(a[i], a[j]), T на 2*min(a[i], a[j]), переопределяем i и j, при необходимости (j==p) переопределяем p как следующее из ранее запомненных.