洛谷 CF141B 题解

洛谷题目传送门 | AT 原题传送门

思路

这道题考察了桶的思想。

定义两个桶，分别存放给出招牌中的每个字母的数量和配件包中的每个字母的数量

有两个小问题需要注意：

1. 当招牌需要这个字母，而配件包里没有，直接输出 $-1$ 并结束程序；

2. 需要特判当配件包里的每个字符数量如果是 $0$，就要跳过本次循环，避免除数为 $0$。

思路不难，看看代码和注释就能理解吧

代码

#include<cmath>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int ta[30],tb[30];
int n,m;
string a,b;
int maxn=-1;
int main()
{
	cin>>n>>m;
	cin>>a>>b;
	for(int i=0;i<n;i++)
	{
		ta[a[i]-'A'+1]++;
	}
	for(int i=0;i<m;i++)
	{
		tb[b[i]-'A'+1]++;
	}
	//上面的两个循环是桶的初始化，记录字符出现的数量
	for(int i=1;i<=26;i++)
	{
		if(ta[i]!=0 && tb[i]==0)//特判输出 -1 的条件
		{
			cout<<-1<<endl;
			return 0;
		}
		if(ta[i]==0 && tb[i]==0)//特判除数为 0 时的情况
		{
			continue;
		}
		maxn=max(maxn,(int)(ceil(1.0*ta[i]/tb[i])));//直接进行计算
	}
	cout<<maxn<<endl;
	return 0;
}

求管理大大通过