自动搬运

查看原文

来自洛谷，原作者为

	Igallta 「この世には愛も知らない人が 沢山いるんですよ」

搬运于2025-08-24 21:16:32，当前版本为作者最后更新于2024-08-07 11:52:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

一共有 $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;