题解 | 小红的素数合并

小小的证明一下，任取四个数x1=x,x2=x+a,x3=x+b,x4=x+c，其中（a<b<c)。

计算得

x1*x4=x²+cx

x2*x3=x²+(a+b)x+a*b

x1*x3=x²+bx

x2*x4=x²+(a+c)x+a*c

观察发现

x1*x3<x2*x3且x1*x3<x1*x4

x2*x4>x1*x4且x1*x4>x2*x3

所以交错乘会使极差增大，故首位相乘。

要注意n为奇数时有一个数没得乘，相当于有个数要乘1，给数组加一个1即可。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long 
signed main() {
    int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    if(n%2){
        n++;
        a.push_back(1);
    }
    sort(a.begin(),a.end());
    int ma=0,mi=1e18;
    for(int i=0;i<n/2;i++){
        int x=a[i]*a[n-i-1];
        ma=max(x,ma);
        mi=min(x,mi);
    }
    cout<<ma-mi<<'\n';
}