本文主要是介绍1255: 石子合并,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
时间限制: 1 Sec 内存限制: 128 MB
提交: 1456 解决: 779
[提交] [状态] [讨论版] [命题人:外部导入]
题目描述
现在有n堆石子,你每次可以挑任意两堆将其合并成一堆,代价是两堆石子的数量和。可知经过n-1次合并后只剩下一堆石子,现在要求总代价最小,请求出合并石子的最小总代价。
输入
第一行一个n(0 < n <= 10000),代表有n堆石子,接下来一行n个由空格分隔的数ai(0 <= ai <= 100000)表示第i堆石子的数目。
输出
输出一行表示答案。
样例输入 Copy
5
1 2 3 4 5
样例输出 Copy
33
来源/分类
贪心
import java.util.*;
//1255
public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();int[] stones = new int[n];for (int i = 0; i < n; i++) {stones[i] = input.nextInt();}input.close();Arrays.sort(stones);long totalCost = 0;for (int i = 1; i < n; i++) {stones[i] += stones[i - 1];totalCost += stones[i];Arrays.sort(stones, i, n);}System.out.println(totalCost);}
}
这篇关于1255: 石子合并的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!