小红的素数合并

标签： 贪心 数学

难度： 适中

思路：

先排序，偶数情况，将最小的和最大的相乘，将倒数第二小和倒数第二大相乘，以此类推，因为偶数最后全需操作为素数。

奇数情况，需舍弃最后一个最大的，然后按偶数处理。

证明：

示例：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
typedef long long ll;
const int N=100010;
ll n,a[N];

int main()
{
	cin>>n;
	rep(i,1,n)
	cin>>a[i];
	sort(a+1,a+1+n);

	ll l=1,r=n-n%2;
	ll mi=1e9,ma=0;
	while(l<r)
	{
		mi=min(mi,a[l]*a[r]);
		ma=max(ma,a[l]*a[r]);
		l++;
		r--;
	}
	if(n&1)
	{
		mi=min(mi,a[n]);
		ma=max(ma,a[n]);
	}
	
	cout<<ma-mi;
	
	return 0;
}