MIUP 2012 Problema C - Um algoritmo ganancioso

A Maratona Inter-Universitaria de Programação (MIUP) 2013 é já no próximo sábado.
A minha última participação foi em 2009 (equipa LuscoFusco) e não tenho seguido com muita atenção as últimas edições da prova. Dada a proximidade da MIUP deste ano, estão disponíveis para treino os problemas de alguns concursos, incluindo os da MIUP 2012. Eu decidi ir resolver os problemas for fun.

Penso que os problemas são equilibrados, com um nível de dificuldade adequado e incluindo alguns problemas com casos particulares para distinguir as equipas com mais atenção ao detalhe. A única critica negativa que faço é ao problema D onde penso que não é claro no enunciado que os carros a colocar num ferry têm de ser consecutivos no input (e isso faz toda a diferença na solução).

O problema que gostei mais foi o problema C - Humanitarian Logistics. Sucintamente, temos N caixas de alimentos, cada uma com um tempo de validade T_i (em dias) e um valor V_i. Em cada dia, podemos escolher uma das caixas cuja validade não tenha expirado para distribuir pela população. O objectivo é minimizar o desperdício, isto é, o valor das caixas cuja validade expira antes de serem entregues, e imprimir os índices (de ordem no input) das caixas que serão entregues por ordem crescente de índice.

Os limites são 1 ≤ N ≤ 100,000;  1 ≤ T_i ≤ N;   1 ≤ V_i ≤ 100,000. Como resolver o problema de forma eficiente?