B4011 [语言月赛 202407] speech 题解

· · 题解

题目大意

一共有 m 种语言，第 i 种语言的语法数量为 a_i。

一共有 n 个居民，第 i 个居民使用的语言为 b_i。

假设语言 i 使用的人数为 c_i，求出第一个最大的 a_i\times c_i。

思路

首先，我们要输入 n、m、数组 a、数组 b。

这道题我们不知道的东西是 c 数组，那我们就要去求得它。

要怎么去求呢？注意到题目给了我们一个 b 数组，这个数组记录的是第 i 个居民使用的语言。那我们就可以通过这个数组来求得 c 数组。

我们可以以一种“统计表”的思想来求出 c 数组，也就是我们说的“桶”。输入一个 b_i，就给 c_{b_i} + 1。

这一步可能理解有一点点困难，可以多看几遍。

这一部分的代码：

cin>>n>>m;
for(int i=1;i<=m;i++){
  cin>>a[i];
} 
for(int i=1;i<=n;i++){
  int k;
  cin>>k;//因为 b 数组不需要储存，所以用了临时变量，当然也可以用 b 数组。
  ++c[k];
}

然后再来看下一个操作：求出第一个最大的 a_i\times c_i。

既然我们有了 c 数组，那么就可以一个循环求出来了！

我们记录 maxn，它代表当前的最大值。再记录 maxi，它代表当前第一个最大值的下标。

有些同学可能会比较疑惑：“你怎么保证它一定是第一个呢？”

其实，我们在比较的时候使用小于或大于符号，而不是小于等于或大于等于符号就可以保证它是第一个且最大了。因为一样大的值并不大于当前的最大值。

这一部分的代码：

for(int i=1;i<=m;i++){
  if(maxn<c[i]*a[i]){
    maxi=i;
    maxn=c[i]*a[i];
  }
}

最后一定一定记得输出 maxi！

cout<<maxi;