@[Linco2012](/user/1165146)
这道题是每次取两个最小的合成,但你合
成后的不一定是最小的
by ycy1124 @ 2024-04-17 15:41:06
@[ycy1124](/user/1199534)
依旧10分
```cpp
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<ctime>
using namespace std;
long long a[10001],ans=0;
bool cmp(int a,int b)
{
return a<b;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1,cmp);
for(int i=2;i<n;i++)
{
a[i]=a[i]+a[i-1];
a[i-1]=0;
for(int j=i;j<=n;j++)
{
if(a[j+1]<a[j]) swap(a[j],a[j+1]);
else break;
}
}
for(int i=1;i<=n;i++)
{
ans+=a[i];
ans+=a[i-1];
}
cout<<ans;
return 0;
}
``````
by Linco2012 @ 2024-04-19 15:25:44
你的用两个数组,一个储存还没合成过一次的,一个储存合成过的,每次取其中最小的两个合成
by ycy1124 @ 2024-04-22 12:34:05
@[Linco2012](/user/1165146)
忘 @ 了
这是我的代码
暴力
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[10001];
int main()
{
int n;
long long js=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n-1;i++)
{
sort(a+i,a+n+1);
js+=a[i];
js+=a[i+1];
a[i+1]+=a[i];
}
cout<<js;
return 0;
}
``````
我开始说的做法
```cpp
#include<bits/stdc++.h>
using namespace std;
queue<long long>a;
queue<long long>b;
long long c[100001];
long long js;
int read(){
int f=1,x=0;
char ch=getchar();
if(ch=='-'){
f=-1;
ch=getchar();}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();}
x*=f;
return x;}
int main(){
int n,x;
n=read();
for(int i=1;i<=n;i++){
x=read();
c[x]++;}
for(int i=1;i<=100000;i++)
for(int j=1;j<=c[i];j++)
a.push(i);
long long s1,s2;
for(int i=1;i<n;i++){
if(b.size()>=2&&a.size()>=2){
if(a.front()<b.front()){
s1=a.front();
a.pop();}
else{
s1=b.front();
b.pop();}
if(a.front()<b.front()){
s2=a.front();
a.pop();}
else{
s2=b.front();
b.pop();
}}
else if(b.empty()&&a.size()>=2){
s1=a.front();
a.pop();
s2=a.front();
a.pop();}
else if(a.empty()&&b.size()>=2){
s1=b.front();
b.pop();
s2=b.front();
b.pop();}
else if(a.size()==1&&b.size()==1){
s1=a.front();
a.pop();
s2=b.front();
b.pop();}
else if(a.size()==1&&b.size()>1){
if(a.front()<b.front()){
s1=a.front();
a.pop();
s2=b.front();
b.pop();}
else{
s1=b.front();
b.pop();
if(a.front()<b.front()){
s2=a.front();
a.pop();}
else{
s2=b.front();
b.pop();}}}
else if(b.size()==1&&a.size()>1){
if(a.front()<b.front()){
s1=a.front();
a.pop();
if(a.front()<b.front()){
s2=a.front();
a.pop();}
else{
s2=b.front();
b.pop();}}
else{
s1=b.front();
b.pop();
s2=a.front();
a.pop();}}
b.push(s1+s2);
js+=s1;
js+=s2;}
cout<<js<<endl;
return 0;}
``````
by ycy1124 @ 2024-04-22 12:38:12
直接用小根堆就好了,没那么难
by Mathhew @ 2024-05-03 12:11:28
@[Linco2012](/user/1165146) 你给我整晕了
by aochiao @ 2024-05-04 12:41:34
@[Linco2012](/user/1165146) 代码如下
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,x,ans=0;
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;
return 0;
}
by aochiao @ 2024-05-04 12:42:14
@[Linco2012](/user/1165146) 求关注QwQ
by aochiao @ 2024-05-04 12:42:52
@[aochiao](/user/1258313) 谢谢,但我已经AC,已关。
by Linco2012 @ 2024-05-07 15:08:10
此贴完
by Linco2012 @ 2024-05-07 15:08:37