Решение задачи Валера и тарелки с Codeforces

С пояснением   Просмотров: 31


Валера — ленивый студент. У него дома имеются m чистых глубоких тарелок и k чистых плоских тарелок.

Валера распланировал, что он будет кушать ближайшие n дней. Поскольку Валера ленив, каждый день он будет есть ровно одно блюдо. При этом, чтобы съесть блюдо, ему нужна ровно одна чистая тарелка. Известно, что Валера умеет готовить всего два типа блюд. Блюда первого типа можно есть только из глубоких тарелок, а блюда второго типа можно есть и из глубоких тарелок, и из плоских тарелок.

Когда Валера поест, тарелка, из которой он ел, становится грязной. Убеждения Валеры не позволяют ему есть из грязных тарелок, поэтому иногда перед едой ему нужно будет помыть тарелку. Определите, какое минимальное количество раз Валере потребуется помыть тарелку, если он будет действовать оптимально.

Код

#include <iostream>

using namespace std;

int main()
{
	int n, m, k, type;
	int ans = 0;
	cin >> n >> m >> k;
	
	for(int i = 0; i < n; i++)
	{
		cin >> type;
		
		if (type == 1)
		{
			if (m == 0)
				ans++;
			else
				m--;
		}
		else
		{
			if (k != 0)
			{
				k--;
				continue;
			}	
			
			if (m != 0)
			{
				m--;
				continue;
			}
			
			ans++;
		}
	}
	
	cout << ans << endl;
}

         

Администратор Photo Автор: Администратор


Будем действовать жадно. Пусть сейчас i-й день, и текущее блюдо типа 1. Тогда если у нас есть чистая глубокая тарелка, то воспользуемся ею. Иначе увеличим ответ. Если текущее блюдо типа 2, то мы сначала попробуем взять плоскую тарелку, а потом глубокую. Если чистых тарелок нет совсем, то увеличим ответ.


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться