nowcoder-893-D Stone

link: Stone

Description:

有n堆石子排成一排，第i堆石子有ai个石子。
每次，你可以选择任意相邻的两堆石子进行合并，合并后的石子数量为两堆石子的和，消耗的体力等价于两堆石子中石子数少的那个。
请问，将所有的石子合并成一堆，你所消耗的体力最小是多少？
输入描述:
第一行是一个整数T(1≤T≤20)，表示样例的个数。
每个样例的第一行是一个整数(1≤n≤10000),表示石子堆的数量。
第二行是n个整数(1≤ai≤1e9)
输出描述:
每行输出一个样例的结果。
示例1
输入
2
2
1 2
1
1
输出
1
0
说明
巨大的输入，请使用C风格的输入。

Intentional analysis:

Because the order of the series is not changeable,so we can use the sum of each item in the series to subtract the largest item.It's the answer.

Click to see Chinese Intentional analysis 一开始看到这道题，我以为是贪心裸题，结果仔细一看，数列的顺序是不能变的。。。然后就没了思路。。。等到比赛结束之后看了大佬思路，恍然大悟。 因为每次能合起来两堆石子，消耗的疲劳度是最小的那个，并且顺序还不能变，所以若想使最后的疲劳度最小，只需要让最大的那堆石头当成最后一组合起来的一个就行。因为最大的那个不管加上其他哪个数之后都会大于那个数。在一次合成中消耗掉这个最大的数并且使它不计算入疲劳度，就可以得到最小的疲劳度。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[10005];
int main()
{
    ll n,t;
    scanf("%lld",&n);
    while(n--)
    {
        scanf("%lld",&t);
        ll sum=0;
        for(ll i=0;i<t;i++)
            {scanf("%lld",&a[i]);sum+=a[i];}
        ll maxx=a[0];
        for(ll i=1;i<t;i++)
            maxx=max(maxx,a[i]);
        printf("%lld\n",sum-maxx);
    }
    return 0;
}
赏