cf 1406b

此题思路当时是有的,主要是debug太久了

主要思路

  1. 一般情况,优先选择绝对值大的,我是正负分开的,选abs大的乘进去。最后如果是负的 那就除掉最后的正数,再乘下一个负数 或者 除掉最后的负数,再乘下一个正数
  2. 特殊1 只有五个数,直接连乘
  3. 特殊2 只有负数,结果必为负,选绝对值小的

细节方面

  • int和long long的混用,导致出现越界。建议参与运算的,需要long long全用
  • 下标的处理,不要乱,一个一个过就好

代码如下

cf 1406b
 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

 

上一篇:D. Hemose in ICPC ?(树的欧拉序)


下一篇:[Acwing]1165. 单词环 spfa判断负环+分数规划