Матч 37, Наилучший отель (BestHotel)

В городе расположено некоторое множество отелей, каждый из которых характеризуется ценой и качеством. Цена i - го отеля содержится в price[i], качество – в quality[i]. Будем говорить, что отель Х непривлекательный, если существует отель Y с не худшими характеристиками (не большей ценой и не меньшим качеством), но при этом одна из характеристик (или обе) строго лучше. По заданным массивам цены price и качества quality необходимо подсчитать количество непривлекательных отелей в городе.

Класс: BestHotel

Метод: int numberOfDisadvantageous(vector<int> price,

vector<int> quality)

Ограничения: price и quality содержат одинаковое количество элементов, от 1 до 50, 1 £ price[i], quality[i] £ 1000.

Вход. Массивы цены price и качества quality, характеризующие отели в городе.

Выход. Количество непривлекательных отелей в городе.

Пример входа

price	quality
{100,200}	{3,3}
{100,200,300}	{5,4,3}
{200,300,100,500,100,100,200}	{7,7,4,8,4,3,6}

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

1

2

3

РЕШЕНИЕ

элементарные вычисления

Просматриваем каждую пару (price[i], quality[i]), соответствующую характеристикам i - го отеля, и запускаем функцию disAdvant(price, quality, i), которая ищет отель, лучший i - го. j - ый отель лучше i - го, если одна из характеристик j - го отеля строго лучше, а вторая – не хуже. Функция disAdvant возвращает 1, если i - ый отель непривлекательный и 0 иначе. В переменной res подсчитываем количество непривлекательных отелей.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

int disAdvant(vector<int> &price,vector<int> &quality,int i)

{

for(int j = 0; j < price.size(); j++)

{

if ((price[j] < price[i]) && (quality[j] >= quality[i])) return 1;

if ((price[j] <= price[i]) && (quality[j] > quality[i])) return 1;

}

return 0;

}

class BestHotel

{

public:

int numberOfDisadvantageous(vector<int> price, vector<int> quality)

{

int i, res;

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

if (disAdvant(price,quality,i)) res++;

return res;

}

};