P7375题解

王老吉的父亲 · 2021-12-22 23:05:23 · 题解

思路解析：

本题其实就是求 a[i] - b[i] 出现的最多次数是几，所以我为大家提供两种思路供大家参考：

1.我们可以用桶解决，具体思路见下面代码中的注释。

2.我们还可以 sort 排序一个数组 c（用来存 a[i] - b[i] 的值）,然后遍历数组 c，如果某一项与前一项相同，那么 cnt++ 即可，如果不相同，进行特判，方法见下面代码注释。

下面这一份是用桶做的AC代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int a[1000010],b[1000010],c[50000010];

int main()
{
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++) cin >> b[i];
    for (int i = 1;i <= n;i++)
    {
        c[a[i] - b[i] + 5000000]++;//下标要记得加一个数，避免a[i] - b[i]是负数
    }
    int maxn = -1e9;
    for (int i = 1;i <= 50000000;i++)
    {
        if (c[i] >= maxn) maxn = c[i];
    }
    cout << maxn;
    return 0;
}

下面展示第2种方法，也就是用 for 循环做的：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int a[1000010],b[1000010],c[1000010];

int main()
{
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++) cin >> b[i];
    for (int i = 1;i <= n;i++) c[i] = b[i] - a[i];
    sort(c + 1,c + n + 1);
    int Maxcnt = 0,cnt = 1;//这里初始值也要设成1
    for (int i = 2;i <= n;i++)//从2到n讨论
    {
        if (c[i] == c[i - 1])
        {
            cnt++;
        }
        else
        {
            if (Maxcnt < cnt) Maxcnt = cnt;
            cnt = 1;//这里要注意初始值是1
        }
    }
    if (Maxcnt < cnt) Maxcnt = cnt;//最后还要判断一下
    cout << Maxcnt;
    return 0;
}

谢谢大家的观看~