世界上最好的题解😄

#include<bits/stdc++.h>
using namespace std;
int n,a[10005],x[10005],j=1,b=1,e=1,sum;
void fun(){
	int t;
	for(int i=1;i<n;i++){
		for(int k=1;k<=2;++k){
			if(b==e)t=a[j++];
			else if(j>n)t=x[b++];
			else if(a[j]<x[b])t=a[j++];
			else t=x[b++];
			x[e]+=t;
		}
		sum+=x[e++];
	}
}
int main(){
	cin>>n;for(int i=1;i<=n;++i)cin>>a[i];
	sort(a+1,a+n+1);
	fun();
	cout<<sum;
	return 0;
}

看完别忘了点赞呦👀️

一眼贪心：

#include<bits/stdc++.h>
using namespace std;
int a[10005],n,ans=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=2;i<=n;i++){
        ans+=a[i-1]+a[i];
        a[i]=a[i]+a[i-1];
        for(int j=i+1;j<=n;j++){
            if(a[j-1]>a[j]) swap(a[j],a[j-1]);
            else break;
        }
    }
    cout<<ans<<endl;
    return 0;
}

[NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

题目分析

这一道题需要体力最小。多多每一次搬运都要把已经合并了的再次搬运，所以要省下体力就必须使合并过后的重量尽可能的小。所以，要排序。还必须是升序

这一题还要很多数据的处理，所以就可以使用优先队列priority_queue容器来维护堆，以此实现快速的动态维护有序数组

*priority_queue容器适配器简要介绍

首先说一下，priority_queue是将$\operatorname{STL}$原有的容器进行封装从而实现某种数据结构（堆，即优先队列。除此之外还有栈和队列）。

定义于头文件<queue>（此部分可以跳过不看，但是如果你看懂了就会避很多坑）

tamplate<
class T,
class Container=std::vector<T>
class Compare=std::less<typename Container::value_type>
>class priority_queue

简单的说一下吧

T: 存储的元素类型

Container: 用于存储元素的底层容器类型。容器必须满足序列容器序列容器( $SequenceContainer$ )的要求，而其迭代器必须满足遗留随机访问迭代器 ( $LegacyRandomAccessIterator$ )的要求。 此外，它还必须提供拥有通常语义的下列函数：

1. front
2. push_back
3. pop_back 标准容器 std::vector 和 std::deque 满足 Compare: 提供严格弱序的比较( $Compare$ )类型 注意compare形参的定义，使得若其第一参数在弱序中先于其第二参数则返回 true 。但因为 priority_queue 首先输出最大（或最小）元素，故“先来”的元素实际上最后输出。即队列头含有按照比较( $Compare$ )所施加弱序的“最后”元素(参考资料：CppReference)

元素访问

top():访问队首元素

容量

empty(): 检查底层容器是否为空

size(): 访问容纳的元素数

修改器

push(x): 将 $x$ 加入到 priority_queue 中，并维护堆（底层容器）

算法

令最少需要 $ans$ 点体力

我们可以将输入的元素加入priority_queue当中，每一次取队首前两个元素 $a$,$b$并将其弹出，相加后加入队首。（ $ans$ 也要与$a$, $b$ 相加）（大前提：底层容器中还有至少两个元素）

最后输出 $ans$ 即可

时间复杂度：$O(n)$

$116\operatorname{ms}$

空间复杂度：$O(n)$

$812\operatorname{KiB}$

代码（ 请勿抄袭 ）

#include<bits/stdc++.h>
using namespace std;
int n,x,ans;
priority_queue<int,vector<int>,greater<int> >q;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>x,q.push(x);
	while(q.size()>=2){
		int a=q.top(); q.pop();
		int b=q.top(); q.pop();
		ans+=a+b;
		q.push(a+b);
	}
	cout<<ans<<endl;
	return 0;
}

注：由于priority_queue的定义，创建对象时必须写成priority_queue<int,vector<int>,greater<int> >q;