Матч 355, Смешивание жидкостей (MixingLiquids)

Дивизион 2, Уровень 3; Дивизион 1, Уровень 2

Если смешать x литров воды со (100 – x) литрами субстанции, получим x% раствор субстанции. Имеется набор бутылок, содержащих растворы одной и той же субстанции. i - ая бутылка содержит amount[i] литров percent[i]% раствора субстанции. Необходимо определить наибольшее количество литров need% раствора, которое можно получить, смешивая содержимое бутылок (возможно, частичное).

Класс: MixingLiquids

Метод: double howMuch(vector<int> percent, vector<int> amount,

int need)

Ограничения: 0 £ percent[i] £ 100, 0 £ amount[i] £ 1000, 0 £ need £ 100.

Вход. Массив percent содержит процентный раствор субстанций в имеющихся бутылках, а amount содержит емкость бутылок. Значение need содержит процентное содержание субстанции, которое следует получить.

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

Пример входа

percent	amount	need
{0, 100}	{20, 30}	50
{90, 70, 80}	{10, 10, 10}	50
{30, 80, 60}	{40, 10, 15}	57

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

40.0

0.0

35.18518518518519

РЕШЕНИЕ

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

Вычислим процентное содержание субстанции в растворе, полученном сливанием жидкостей со всех бутылок. Для этого следует найти общее количество субстанции и общий объем жидкости. Если полученное процентное содержание меньше (больше) требуемого значения need, то следует изъять из раствора бутылку с наименьшим (наибольшим) процентом содержания субстанции. Очевидно, что в таком случае процентное содержание субстанции в общем растворе увеличится (уменьшится). Продолжаем процесс последовательного изъятия из общего раствора бутылок, пока процентное содержание субстанции не пересечет значение need. Предположим, что указанное пересечение значения need произошло как раз на i-ой бутылке. Значит, нам необходимо взять из i-ой бутылки какую-то часть раствора, чтобы получить в точности need% раствор.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <numeric>

#include <set>

#include <algorithm>

using namespace std;

class MixingLiquids

{

public:

double howMuch(vector<int> percent, vector<int> amount, int need)

{

int i,j,totSubstance,

totAmount = accumulate(amount.begin(),amount.end(),0);

vector<pair<int,int> > v;

for(totSubstance=i=0;i<percent.size();i++)

totSubstance += percent[i]*amount[i];

for(i=0;i<percent.size();i++)

v.push_back(make_pair(percent[i],amount[i]));

sort(v.begin(),v.end());

i = 0; j = v.size()-1;

while(i<=j)

{

if (totSubstance == need*totAmount) return totAmount;

if (totSubstance < need*totAmount)

{

int _totSubstance = totSubstance - v[i].first*v[i].second;

int _totAmount = totAmount - v[i].second;

if (_totSubstance > need*_totAmount)

return _totAmount+

1.0*(need*_totAmount - _totSubstance)/(v[i].first - need);

else

{

totSubstance = _totSubstance;

totAmount = _totAmount;

i++;

}

}

if (totSubstance > need*totAmount)

{

int _totSubstance = totSubstance - v[j].first*v[j].second;

int _totAmount = totAmount - v[j].second;

if (_totSubstance < need*_totAmount)

return _totAmount+

1.0*(need*_totAmount - _totSubstance)/(v[j].first - need);

else

{

totSubstance = _totSubstance;

totAmount = _totAmount;

j--;

}

}

}

return 0;

}

};