列表

详情


NC25576. Stone

描述

有n堆石子排成一排,第i堆石子有a_i个石子。
每次,你可以选择任意相邻的两堆石子进行合并,合并后的石子数量为两堆石子的和,消耗的体力等价于两堆石子中石子数少的那个。
请问,将所有的石子合并成一堆,你所消耗的体力最小是多少?

输入描述

第一行是一个整数,表示样例的个数。
每个样例的第一行是一个整数,表示石子堆的数量。
第二行是n个整数

输出描述

每行输出一个样例的结果。

示例1

输入:

2
2
1 2
1
1

输出:

1
0

说明:

巨大的输入,请使用C风格的输入。

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 69ms, 内存消耗: 476K, 提交时间: 2019-05-04 22:13:00

#include <bits/stdc++.h>
using namespace std;
long long a[100005];

int main()
{
	int t,n;
	cin>>t;
	while(t--)
	{
		long long s=0;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			s+=a[i];
		}
		sort(a+1,a+1+n);
		cout<<s-a[n]<<endl;
	}
	return 0;
}

C(clang 3.9) 解法, 执行用时: 25ms, 内存消耗: 1144K, 提交时间: 2019-05-05 18:41:10

#include<stdio.h>
int main()
{
	long long int a,i,j,s;
	int n,m,max;
	scanf("%d",&m);
	while(m--){
		s=0;max=0;
		scanf("%d",&n);
		while(n--){
			scanf("%lld",&a);
			s+=a;
			if(a>max) 
				max=a;
		}
		printf("%lld\n",s-max);
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 18ms, 内存消耗: 488K, 提交时间: 2019-05-04 21:34:38

#include<stdio.h>
int t,n;
long long int m,num,max;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		max=0,num=0;
		scanf("%d",&n);
		while(n--)
		{
			scanf("%lld",&m);
			num+=m;
			if(max<m)
			max=m;
		}
		printf("%lld\n",num-max);
	}
}

Python3(3.5.2) 解法, 执行用时: 34ms, 内存消耗: 4828K, 提交时间: 2020-09-22 20:09:29

n=int(input())
while n:
    lenth=int(input())
    list1=list(map(int,input().split()))
    print(sum(list1)-max(list1))
    n-=1

pypy3 解法, 执行用时: 107ms, 内存消耗: 32236K, 提交时间: 2022-09-12 19:55:56

for s in [*open(0)][2::2]:
    print(sum(sorted(map(int, s.split()))[:-1]))
        
    

上一题