题目描述

𝐴𝑟𝑖𝑎接到了一份来自校方的委托，虽然没有学分但也必须完成。
需要粉刷𝑛条木板，这些木板按照左端对齐，每条木板的高度都是1，
第𝑖条木板的长度为𝐴𝑖。
𝐴𝑟𝑖𝑎只有一个宽度为1的刷子，她每次可以水平或者竖直地对连续的
位置进行粉刷，刷子不能经过没有木板的位置。
𝐴𝑟𝑖𝑎对校方的这个安排非常不满，但为了效率，她允许重复粉刷一个
位置，希望通过最少的次数来完成这𝑛条木板的粉刷。

输入描述: 

第一行，一个正整数𝑛。
第二行，𝑛个正整数𝐴𝑖。

输出描述: 

一行，一个整数，需要进行的最小粉刷次数。

思路：这一题的思路上面那一位名为savage大佬已经讲得很清楚了。
简单来说，本题的解法就是：每一次取出数组中的长度最小的2个木块，并将其合并，同时成本+合并之后的木块长度，并且将合并后的这个木块放回数组中，以此类推，直到木块数量=1时结束
上面大佬的解法是用小根堆做的，运行速度很快，平均只要5-6ms就AC了
但是如果不知道小根堆的话，也可以不用小根堆，就是会慢很多
第一次想的是每次循环都用sort解，但是测试点9超时了
代码如下
#include<stdio.h>
#include<bits/stdc++.h>
long long int a[40020]={0};
using namespace std;
int main(){
    int n,i;
    long long int sum=0;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%lld",&a[i]);
    }
    for(i=0;i<n-1;i++){
        sort(a+i,a+n);
        sum+=(a[i]+a[i+1]);
        a[i+1]=(a[i]+a[i+1]);
    }
    printf("%lld\n",sum);
    return 0;
}
之后加了快读函数，同时优化了sort范围，发现测试点9始终过不去
于是就换了一种方法，手动遍历查询最小值和次小值，然后就AC了......
AC代码如下（不用小根堆）:
#include<stdio.h>
#include<bits/stdc++.h>
long long int a[20020]={0};
using namespace std;
int main(){
    int n,i,j,p,q;
    long long int sum=0;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%lld",&a[i]);
    }
    sort(a,a+n); 
    for(i=0;i<n-1;i++){
        p=0;q=1;
        if(a[p]>a[q]) swap(a[p],a[q]);
        for(j=2;j<n-i;j++){
            if(a[p]>a[j]){
                q=p;
                p=j;
            }
            else if(a[q]>a[j]) q=j;
        }
        sum+=(a[p]+a[q]);
        a[p]=(a[p]+a[q]);
        a[q]=a[n-1-i];
    }
    printf("%lld\n",sum);
    return 0;
}