小红的素数合并时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小红拿到了一个数组其中每个元素都是素数。小红准备进行若干次以下操作选择两个素数元素将他们合并生成的新元素为原来两个素数的乘积。现在小红希望操作到不能再操作为止然后使得最终的极差最大值减最小值尽可能小。你能帮帮她吗输入描述第一行输入一个正整数n nn代表小红拿到的数组。第二行输入n nn个正整数a i a_iai​​代表数组中的元素。保证a i a_iai​​是素数。1 ≤ n ≤ 10 5 1≤n≤10^51≤n≤1052 ≤ a i ≤ 10 9 2≤a_i≤10^92≤ai​≤109输出描述一个整数代表合并后的数组的极差。示例1输入4 2 3 5 3输出1说明合并两次分别合并2 , 5 2,52,5以及3 , 3 3,33,3形成的数组是[ 9 , 10 ] [9,10][9,10]极差是10 − 9 1 10-9110−91。解题思路本题核心是贪心配对策略结合质数合并规则求解最小极差。数组元素全为质数仅能两两合并为乘积最终元素数量固定偶数个元素合并为n / 2 n/2n/2个奇数个元素保留1个单独值、剩余合并为( n − 1 ) / 2 (n-1)/2(n−1)/2个。要让最终数组极差最小最优方案为排序后首尾配对将数组从小到大排序用最小数乘最大数、次小数乘次大数该策略能让所有乘积数值尽可能接近。最后计算合并后数组的最大值与最小值的差值即为所求最小极差。算法时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)完美适配n ≤ 10 5 n \le 10^5n≤105的数据规模。总结核心逻辑质数只能两两合并首尾配对相乘可让乘积最接近实现极差最小化。关键操作数组升序排序、首尾贪心配对相乘、计算最终极差。效率保障排序线性遍历无冗余计算轻松处理十万级数据量。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidsolve(){ll n;cinn;vectorlla(n1);for(ll i1;in;i){cina[i];}sort(a.begin()1,a.end());vectorllb(n/21);if(n%20){for(ll i1;in/2;i){b[i]a[i]*a[n-i1];}sort(b.begin()1,b.end());coutb[n/2]-b[1]\n;}else{b[0]a[n];for(ll i1;in/2;i){b[i]a[i]*a[n-i];}sort(b.begin(),b.end());coutb[n/2]-b[0]\n;}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T1;//cinT;while(T--){solve();}return0;}