リンク

リンクテキスト

質問する

n個の整数からなる数列があります.この数列から1つの整数を削除したり、2つの整数を削除したりできます.整数を1つ削除すると、その整数はスコアになります.2つの整数を削除すると、2つの整数の積はスコアになります.この手順を繰り返します.数列に残りがない場合は、点数の合計の最大値を求めるプログラムを作成します.
例えば、−1,5,3,5,1等の数列.まず1を取り除き、それから5と5を取り除き、それから-1と-3を取り除きます.この場合、点数はそれぞれ1、25、3で、合計は29となります.

入力

第1行は整数n(1≦n≦100000)を与える.次のn行では、n個の節値が1000000を超えない整数が与えられる.

しゅつりょく

最初の行に最大スコアを出力します.

に答える

n個の整数の絶対値は1000000に達する可能性があるため、非常に大きな整数になる可能性が高い.だからlong doubleじゃない
BigIntegerタイプを使用する必要があります.次に、値の整数、負数、および1の配列を生成します.整数または負数の配列の長さが偶数であれば2個を乗じ、配列の長さが奇数であれば2個を乗じ、残りの1個は加算するだけです.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class practice {
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		BigInteger answer=new BigInteger("0");
		
		ArrayList<Long> plus=new ArrayList<Long>();
		ArrayList<Long> minus=new ArrayList<Long>();
		ArrayList<Long> one=new ArrayList<Long>();
		
		for(int i=0; i<n; i++)
		{
			long num=Integer.parseInt(br.readLine());
			if(num==1)
				one.add(num);
			else if(num>1)
				plus.add(num);
			else if(num<=0)
				minus.add(num);
		}
		
		Collections.sort(plus, Collections.reverseOrder());
		Collections.sort(minus);
		
		if(plus.size()%2==0)
		{
			for(int i=0; i<plus.size(); i+=2)
				answer=answer.add(BigInteger.valueOf(plus.get(i)*plus.get(i+1)));
		}
		
		else if(plus.size()%2!=0)
		{
			for(int i=0; i<plus.size()-1; i+=2)
				answer=answer.add(BigInteger.valueOf(plus.get(i)*plus.get(i+1)));
			answer=answer.add(BigInteger.valueOf(plus.get(plus.size()-1)));
		}
		
		if(minus.size()%2==0)
			for(int i=0; i<minus.size(); i+=2)
				answer=answer.add(BigInteger.valueOf(minus.get(i)*minus.get(i+1)));
		
		else if(minus.size()%2!=0)
		{
			for(int i=0; i<minus.size()-1; i+=2)
				answer=answer.add(BigInteger.valueOf(minus.get(i)*minus.get(i+1)));
			answer=answer.add(BigInteger.valueOf(minus.get(minus.size()-1)));
		}
		
		long one_size=one.size();
		answer=answer.add(BigInteger.valueOf(one_size));
		System.out.println(answer);
		
		
	}
}