题解：P14297 [JOI2023 预选赛 R2] 年龄之差 / Age Difference

lizongrui000 · 2025-10-23 09:21:25 · 题解

分析题目

有 N 个居民，每个居民都有自己的年龄 A_i，其中 1 \le i \le N，求每个居民与其他居民的最大年龄差。

代码思路

考虑直接按题意模拟，套两层循环，第一层为当前要输出的最大年龄差，第二层则是依次枚举年龄差，用 maxn 存储最大值，若下标相同就跳过。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n+5];
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;++i)
    {
        int maxn=0;
        for(int j=1;j<=n;++j)
        {
            if(i==j) continue;
            maxn=max(maxn,abs(a[i]-a[j]));
        }
        cout<<maxn<<endl;
    }
    return 0;
}

但是这样时间复杂度为 \mathcal O(N^2)，但 2 \le N \le 250 \, 000，交上去会被 TLE 制裁。想到年龄差最大只能是和极值（最大值和最小值）相减的绝对值，所以再定义一个新数组存储年龄，然后用 sort 排序，然后在输出最大年龄差的那层循环一次把每个年龄都减去最大值和最小值，然后再输出最大值的绝对值和最小值的绝对值中更大的那一个就行了。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n+5],b[n+5];
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    for(int i=1;i<=n;++i)
    {
        int maxn=0;
        maxn=max(abs(a[i]-b[1]),abs(a[i]-b[n]));
        cout<<maxn<<endl;
    }
    return 0;
}

交上去后可以 AC，成功制裁 TLE。记录。

不过，这份代码仍然可以优化，在输入时寻找最大值和最小值，最大值初始赋值一个负数，然后与每个数比较，用 max 函数就行了。最小值初始赋值一个极大的数，与每个数比较，用 min 函数，这样不需要排序就能得出最大值和最小值了，然后跟之前一样。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n+5],maxn=-1,minn=1000000005;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        maxn=max(maxn,a[i]);
        minn=min(minn,a[i]);
    }
    for(int i=1;i<=n;++i)
    {
        int maxnn=0;
        maxnn=max(abs(a[i]-minn),abs(a[i]-maxn));
        cout<<maxnn<<endl;
    }
    return 0;
}