1.题号:NC25519

2.题目原文:

小红拿到了一个数组，其中每个元素都是素数。小红准备进行若干次以下操作： 选择两个素数元素，将他们合并，生成的新元素为原来两个素数的乘积。 现在小红希望操作到不能再操作为止，然后使得最终的极差（最大值减最小值）尽可能小。你能帮帮她吗？

- 输入描述:

• 第一行输入一个正整数n，代表小红拿到的数组。
• 第二行输入n个正整数ai，代表数组中的元素。保证ai是素数。

输出描述:

• 一个整数，代表合并后的数组的极差。

3.牛客OJ链接：https://ac.nowcoder.com/acm/problem/273647

4.思路:

• 显然，第一步应当将数据排序；
• 对于偶数个数据，应该首尾相乘，并判断最值，最值相减可得最小极差；
• 对于奇数个数据，应该除去最大元素首尾相乘，并判断最值，再用原最大值更新最值，最值相减可得最小极差。

5.代码:

using namespace std;
typedef long long ll;
const int N = 1e5+9;
const ll M = 1e18+9;
ll a[N];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    ll mi=M,ma=0;
    
    if(n&1)
    {
        int l=1,r=n-1;
        while(l<r)
        {
            mi=min(mi,a[l]*a[r]);
            ma=max(ma,a[l]*a[r]);
            l++;r--;
        }
        mi=min(mi,a[n]);
        ma=max(ma,a[n]);
    }
    else
    {
        int l=1,r=n;
        while(l<r)
        {
            mi=min(mi,a[l]*a[r]);
            ma=max(ma,a[l]*a[r]);
            l++;r--;
        }
    }
    cout<<ma-mi;
    return 0;
}