石子游戏

蓝桥杯 石子游戏

问题描述
　　石子游戏的规则如下：
　　地上有n堆石子，每次操作可选取两堆石子（石子个数分别为x和y）并将它们合并，操作的得分记为(x+1)×(y+1)，对地上的石子堆进行操作直到只剩下一堆石子时停止游戏。
　　请问在整个游戏过程中操作的总得分的最大值是多少？
输入格式
　　输入数据的第一行为整数n，表示地上的石子堆数；第二行至第n+1行是每堆石子的个数。
输出格式
　　程序输出一行，为游戏总得分的最大值。
样例输入
10
5105
19400
27309
19892
27814
25129
19272
12517
25419
4053
样例输出
15212676150
数据规模和约定
　　1≤n≤1000，1≤一堆中石子数≤50000

一定要注意这里 arr 数组必须使用long，否则得不到正确的结果。
我一开始看到一堆石子数是小于50000用int是足够的，我也不清楚为什么，不是说int能表示-2^31~231-1范围的数吗？有人知道原因，留个解答，感谢

import java.util.Scanner;

public class Main {
	static long[] arr = new long[1002];
	static int n;
	static long result = 0;
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		for(int i=0;i<n;i++){
			arr[i] = sc.nextInt();
		}
		QuickSort(arr, 0, n-1);
		System.out.println(f(arr, n-1));
	}
	
	private static long f(long[] arr,int step){
		if(step==0)
			return result;
		result += (arr[step] + 1) * (arr[step-1] + 1);
		arr[step-1] += arr[step];
		return f(arr, step-1);
	}

	private static void QuickSort(long[] arr,int left,int right){
		if(left < right){
			int q = partition(arr, left, right);
			QuickSort(arr, left, q-1);
			QuickSort(arr, q+1, right);
		}
	}
	
	private static int partition(long[] arr,int left,int right){
		long temp = arr[left];
		while(left!=right){
			while(left < right && arr[right] >= temp)
				right--;
			arr[left] = arr[right];
			while(left < right && arr[left]<=temp)
				left++;
			arr[right] = arr[left];
		}
		arr[left] = temp;
		return left;
	}
}