[题解]合并果⼦三种⽅法博主与合并果⼦⽃争许久了，最初接触到的便是贪⼼。
于是就有如下双队列的⽅法。
#include <ctime>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define re return
#define s(a) sizeof(a)
#define maxx(a,b,c) max(max(a,b),c)
#define minx(a,b,c) min(min(a,b),c)
#define up(i,m,n) for(int i=m;i<=n;i++)
#define down(i,m,n) for(int i=n;i>=m;i--)
using namespace std;
const int MAXN=30005;
int a[MAXN],b[MAXN],n;
inline int init()
{加龄臭
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n);
memt(b,67,s(b));
}
inline int solve()
{
int h1=0,t1=n,h2=0,t2=0;
int ans=0;
while (t1-h1+t2-h2>1)
{
int temp=0;
if (h1==t1||h2<t2&&b[h2+1]<a[h1+1])//first
temp+=b[++h2];
el
temp+=a[++h1];
if (h1==t1||h2<t2&&b[h2+1]<a[h1+1])//cond
temp+=b[++h2];
el
temp+=a[++h1];
ans+=temp;
b[++t2]=temp;
}
return ans;
}
int main()
{
init();
cout<<solve()<<endl;
return 0;
}
之后⼜学了堆(heap)
于是便有⼀个感觉，堆就是为合并果⼦⽽⽣的啊！以下是⼿打堆，
婀娜的意思是注意堆的get( )与put( )；
一岁宝宝发型#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<ctime>
江西高考分数线
#define re return
#define LL long long
#define s(a) sizeof(a)
#define clr(a,x) memt(x,a,s(x))
#define mint(a,b,c) min(min(a,b),c)
#define maxt(a,b,c) max(max(a,b),c)
中国左翼作家联盟#define up(i,m,n) for (int i=m;i<=n;i++)
#define down(i,m,n) for (int i=n;i>=m;i--)
using namespace std;
const int MAXN=100005;
int heap[MAXN];
int len=0,n=0;
void put(int x)
{
int pos,ne;
heap[++len]=x;
pos=len;
while(pos>1)
{
ne=pos>>1;
if (heap[pos]>=heap[ne])return;
swap(heap[pos],heap[ne]);
pos=ne;
}
}
int get()
{
int pos,ans=0,ne;
ans=heap[1];
heap[1]=heap[len--];
pos=1;
while(pos*2<=len)
{
ne=pos*2;
if(ne<len&&heap[ne+1]<heap[ne]) ne++;
if (heap[pos]<=heap[ne]) return ans;
swap(heap[pos],heap[ne]);
pos=ne;
}
return ans;
}
int solve()
{
int tot=0;int a;
up(i,1,n)
cin>>a,put(a);
up(i,1,n-1)
{
int x;
x=get();
int y;
y=get();
y=get();
tot+=x+y;
put(x+y);
}
re tot;
}
int main()
{
freopen("fruit.in","r",stdin);
freopen("fruit.out","w",stdout);
cin>>n;
cout<<solve()<<endl;
re 0;
}
然⽽ C++的STL提供了⼀个⽜B的东西，优先队列
priority_queue< int,vector<int>,greater<int> > h;
这是⼀个优先队列h，(greater<int>) 表⽰⼩根堆，即跟为最⼩值；若要求⼤根堆，则不加greater<int>；
代码如下
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <iostream>
全国5a景区名单#include <algorithm>
#define re return
#define s(a) sizeof(a)
#define maxx(a,b,c) max(max(a,b),c)
#define minx(a,b,c) min(min(a,b),c)
#define up(i,m,n) for(int i=m;i<=n;i++)
#define down(i,m,n) for(int i=n;i>=m;i--)
using namespace std;
const int MAXN=30005;
priority_queue< int,vector<int>,greater<int> > h;//优先队列;
int main()
{
int n,t;
ios::sync_with_stdio(fal);
cin>>n;
up(i,1,n)
cin>>t,h.push(t);
int ans=0;
up(i,1,n-1)
{
int x,y;
p();h.pop();
p();h.pop();
ans+=x+y;
h.push(x+y);
}
cout<<ans<<endl;
re 0;
}
⾮常强⼤；
但是，但是，博主昨晚睡觉是YY出了很强的⽅法，有受堆的思想的影响；
若每次都是取最⼩的⼀个，为什么不把最⼩的放在队尾，每次去最后⼀个，放⼊时⽤⼀个sort不就好了么于是
#include <cstring>
#include <map>
#include <stack>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define re return
#define clr(a,b) memt(b,a,s(a))
#define s(a) sizeof(a)
#define maxx(a,b,c) max(max(a,b),c) #define minx(a,b,c) min(min(a,b),c)
#define up(i,m,n) for(int i=m;i<=n;i++) #define down(i,m,n) for(int i=n;i>=m;i--) using namespace std;
const int MAXN=30005;
int f[MAXN],n;
bool cmp(const int &a,const int &b)
{
return a>b;
}
void init()
{
scanf("%d",&n);
up(i,1,n)
scanf("%d",f+i);
sort(f+1,f+1+n,cmp);
}
int make()
{
return f[--n+1];
}
int push(int x)
{
f[++n]=x;
sort(f+1,f+1+n,cmp);
厨师长的工作职责}
int main()
{
freopen("fruit.in","r",stdin);
freopen("fruit.out","w",stdout);
ios::sync_with_stdio(fal);
int ans=0;
init();
int len=n;
up(i,1,len-1)
{
int x=make();
int t=make();
push(x+t);
ans+=x+t;
}
cout<<ans<<endl;
幼儿园小班周计划re 0;
}
果断超时，最慢的12.9s；
汗
