2008, TCHS, Весна, Раунд 1, Кофейная (TaliluluCoffee)

В университете Таилулу имеется кофейня. Все посетители прибывают в момент времени 0. На обслуживание одного посетителя требуется одна секунда. Первого посетителя начинают обслуживать в секунду 0. Если i - ый посетитель обслуживается в t - ую секунду, то он платит tips[i] – t чаевых. Если значение tips[i] – t отрицательно, то i - ый посетитель ничего не платит. Массив tips описывает размеры чаевых всех посетителей. Найти наибольшую сумму чаевых, которую можно заработать.

Класс: TaliluluCoffee

Метод: int maxTip(vector<int> tips)

Ограничения: tips содержит от 0 до 50 элементов, 0 £ tips[i] £ 100000.

Вход. Массив tips, описывающий размеры чаевых посетителей.

Выход. Наибольшая сумма чаевых, которую можно заработать.

Пример входа

tips

{3, 3, 3, 3}

{7, 8, 6, 9, 10}

{1, 1, 1, 1, 2}

Пример выхода

6

30

2

РЕШЕНИЕ

жадный алгоритм

Начинать обслуживание следует с тех посетителей, которые больше платят. Отсортируем посетителей в убывающем порядке их размеров чаевых. Проходим по отсортированному массиву tips, суммируя в переменной res размеры чаевых.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

#include <set>

using namespace std;

class TaliluluCoffee

{

public:

int maxTip(vector<int> tips)

{

int i,res;

sort(tips.begin(),tips.end(),greater<int>());

for(res=i=0;i<tips.size();i++)

if (tips[i]-i > 0) res = res + tips[i]-i;

return res;

}

};