HDOJ 5504-GT and sequence

秒速五厘米 2022-08-20 02:18 141阅读 0赞

# GT and sequence #

Accepts: 95

Submissions: 1467

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Problem Description

You are given a sequence of N  integers. You should choose some numbers(at least one),and make the product of them as big as possible. It guaranteed that **the absolute value of** any product of the numbers you choose in the initial sequence will not bigger than 2 63 −1 .

Input

In the first line there is a number T  (test numbers). For each test,in the first line there is a number N ,and in the next line there are N  numbers. 1≤T≤1000 1≤N≤62  You'd better print the enter in the last line when you hack others. You'd better not print space in the last of each line when you hack others.

Output

For each test case,output the answer.

Sample Input

Copy

1
    3
    1 2 3

Sample Output

Copy

解题思路：

题目大意很简单就是从一串数中挑出一些数，将其相乘，所得的结果是最大值。注意这里将包含负数，所以将分开讨论，对于正数在输入时就要累成处理，对于负数要注意负数的个数，和0的个数。

参考数据：

20
    2
    -1 0
    0
    3
    -2 3 0
    3
    5
    -2 3 -2 3 -2
    36
    5
    0 0 0 0 0
    0
    1
    0
    0
    3
    -2 -9 3
    54

剩下要注就是__int64的定义。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    __int64 map[2000];//负数 
    __int64 map1[2000];//正数 
    __int64 uz,uf,u0;
    using namespace std;
    bool cmp(__int64 x,__int64 y)
    {
    	return x<y;
    }
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	while(T--)
    	{
    		__int64 hh=1,hu=1;
    		__int64 N,uu;
    		scanf("%I64d",&N);
    		__int64 i,j;
    		uz=uf=u0=0;
    		for(i=0;i<N;i++)
    		{
    			scanf("%I64d",&uu);
    			if(uu==0)
    			u0++;
    			if(uu<0)
    			{
    				map[uf]=uu*(-1);
    				hu=hu*(uu*(-1));
    				uf++;
    			}
    			if(uu>0)
    			{
    				map1[uz]=uu;
    				hh*=uu;
    				uz++;
    			}
    		}
    		sort(map,map+uf,cmp);
    		if(uz==0&&u0==0&&uf>0)
    		{
    			if(uf%2==0)
    			{
    				printf("%I64d\n",hu);
    			}
    			else
    			{
    				if(uf==1)
    				{
    					printf("%I64d\n",hu*(-1));
    				}
    				else
    				printf("%I64d\n",hu/map[0]);
    			}
    		}
    		if(uz==0&&u0>0&&uf==0)
    		{
    			printf("0\n");
    		}
    		if(uz==0&&u0>0&&uf>0)
    		{
    			if(uf%2==0)
    			{
    				printf("%I64d\n",hu);
    			}
    			else
    			{
    				if(uf==1)
    				printf("0\n");
    				else
    				printf("%I64d\n",hu/map[0]);
    			}
    		}
    		if(uz>0&&u0==0&&uf==0)
    		{
    			printf("%I64d\n",hh);
    		}
    		if(uz>0&&u0==0&&uf>0)
    		{
    			if(uf%2==0)
    			{
    				printf("%I64d\n",hu*hh);
    			}
    			else
    			{
    				printf("%I64d\n",hh*(hu/map[0]));
    			}
    		}
    		if(uz>0&&u0>0&&uf==0)
    		{
    			printf("%I64d\n",hh);
    		}
    		if(uz>0&&u0>0&&uf>0)
    		{
    			if(uf%2==0)
    			{
    				printf("%I64d\n",hu*hh);
    			}
    			else
    			{
    				printf("%I64d\n",hh*(hu/map[0]));
    			}
    		}
    	}
    	return 0;
    }