此题思路当时是有的,主要是debug太久了
主要思路
- 一般情况,优先选择绝对值大的,我是正负分开的,选abs大的乘进去。最后如果是负的 那就除掉最后的正数,再乘下一个负数 或者 除掉最后的负数,再乘下一个正数
- 特殊1 只有五个数,直接连乘
- 特殊2 只有负数,结果必为负,选绝对值小的
细节方面
- int和long long的混用,导致出现越界。建议参与运算的,需要long long全用
- 下标的处理,不要乱,一个一个过就好
代码如下
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define F(i,b,n) for(int i=(b);i<(n);i++) 5 #define f(i,b,n) for(int i=(b);i<=(n);i++) 6 7 typedef long long ll; 8 9 const char* turns="FLR"; 10 const char* dires="ESWN"; 11 12 ll num1[100010],num2[100010]; 13 14 15 int main() 16 { 17 int T,n,top1,top2; 18 ll mul=1; 19 scanf ("%d",&T); 20 while (T--) 21 { 22 memset(num1,0,sizeof(num1)); 23 memset(num2,0,sizeof(num2)); 24 bool flag=false; 25 mul=1; 26 top1=top2=0; 27 int denum=0; 28 29 scanf ("%d",&n); 30 F(i,0,n) 31 { 32 ll num; 33 scanf ("%lld",&num); 34 if (num>=0) num1[top1++]=num; 35 else num2[top2++]=num; 36 } 37 38 sort(num1,num1+top1); 39 sort(num2,num2+top2); 40 41 if (n==5) 42 { 43 f(i,0,top1-1) mul*=num1[i]; 44 f(i,0,top2-1) mul*=num2[i]; 45 printf("%lld\n",mul); 46 continue; 47 } 48 49 if (top1==0) mul=num2[top2-1]*num2[top2-2]*num2[top2-3]*num2[top2-4]*num2[top2-5]; 50 else 51 { 52 top1--,top2--; 53 int cur1=top1,cur2=0; 54 f(i,1,5) 55 { 56 if ( cur1<0 ) 57 { 58 mul*=num2[cur2]; cur2++; denum++; 59 } 60 else if ( cur2>top2 || abs(num1[cur1])>=abs(num2[cur2])) 61 { 62 mul*=num1[cur1]; cur1--; 63 } 64 else 65 { 66 mul*=num2[cur2]; cur2++; denum++; 67 } 68 } 69 if (denum%2==1) 70 { 71 ll mull1=-1e17,mull2=-1e17; 72 if ( cur2!=0 && cur1<=top1 && cur1>=0) 73 { 74 mull1=mul/num2[cur2-1]*num1[cur1]; 75 } 76 if ( num1[cur1+1]!=0 && cur2<=top2 && cur2>=0) 77 { 78 mull2=mul/num1[cur1+1]*num2[cur2]; 79 } 80 mul=max(mul,mull1); 81 mul=max(mul,mull2); 82 } 83 } 84 printf("%lld\n",mul); 85 } 86 return 0; 87 }View Code