首页 > 代码库 > codeforces A. Valera and Plates 题解

codeforces A. Valera and Plates 题解

2024-07-02 08:30:42   223人阅读

Valera is a lazy student. He has m clean bowls and k clean plates.

Valera has made an eating plan for the next n days. As Valera is lazy, he will eat exactly one dish per day. At that, in order to eat a dish, he needs exactly one clean plate or bowl. We know that Valera can cook only two types of dishes. He can eat dishes of the first type from bowls and dishes of the second type from either bowls or plates.

When Valera finishes eating, he leaves a dirty plate/bowl behind. His life philosophy doesn‘t let him eat from dirty kitchenware. So sometimes he needs to wash his plate/bowl before eating. Find the minimum number of times Valera will need to wash a plate/bowl, if he acts optimally.

Input

The first line of the input contains three integers n, m, k (1?≤?n,?m,?k?≤?1000) — the number of the planned days, the number of clean bowls and the number of clean plates.

The second line contains n integers a1,?a2,?...,?an (1?≤?ai?≤?2). If ai equals one, then on day i Valera will eat a first type dish. If ai equals two, then on day i Valera will eat a second type dish.

Output

Print a single integer — the minimum number of times Valera will need to wash a plate/bowl.

Sample test(s)
input
3 1 1
1 2 1
output
1
input
4 3 1
1 1 1 1
output
1
input
3 1 2
2 2 2

本题也是使用暴力法了。

最难的就是读懂题目了。原来这个家伙这么赖，一次只洗一个碗，从不肯多洗。

有两个思路：

1 模拟他洗碗的过程

2 计算多少碟菜，多少个碗和碟，然后进行加减处理

两种方法都需要O(n)时间效率。

方法1：

void ValeraandPlates()
{
	int days, b, p, dishType, times = 0;
	cin>>days>>b>>p;
	for (int t = 0; t < days; t++)
	{
		cin>>dishType;
		if (1 == dishType)
		{
			if (b <= 0)
			{
				times++;
			}
			b--;
		}
		else
		{
			if (b <= 0 && p <= 0)
			{
				times++;
			}
			if (p) p--;
			else b--;
		}
	}
	cout<<times;
}

方法二：

void ValeraandPlates_2()
{
	int days, b, p, dishType, times = 0, A[3] = {0};
	cin>>days>>b>>p;
	for (int t = 0; t < days; t++)
	{
		cin>>dishType;
		A[dishType]++;
	}
	A[2] -= p;
	if (A[2] >= 0) b -= A[2] + A[1];
	else b -= A[1];

	if (b >= 0) cout<<0;
	else cout<<-b;
}


联系
我们