合并果子
題目描述
在一個果園里，多多已經將所有的果子打了下來，而且按果子的不同種類分成了不同的堆，多多決定把所有的果子合成一堆，
每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和，可以看出，所有的果子經過 ( n ? 1 ) (n - 1) (n?1) 次合并之后， 就只剩下一堆了，多多在合并果子時總共消耗的體力等于每次合并所耗體力之和，
因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節省體力，假定每個果子重量都為 1 1 1，并且已知果子的種類數和每種果子的數目，你的任務是設計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的體力耗費值，
Link
O ( n log ? n ) O(n\log n) O(nlogn)
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#define ll long long
using namespace std;
priority_queue<ll,vector<ll>,greater<ll> >q;
int main()
{
int n;
cin>>n;
while(n--)
{
ll x;
scanf("%lld",&x);
q.push(x);
}
ll ans=0;
while(q.size()>=2)
{
ll _=q.top();
q.pop();
ll __=q.top();
q.pop();
ans+=_+__;
q.push(_+__);
}
cout<<ans<<endl;
return 0;
}
加強版
做完之后我們發現還有一道加強版，這個資料范圍看
O
(
n
log
?
n
)
O(n\log n)
O(nlogn) 的演算法就不行了，
時間都去哪了？我們發現不少時間耗費在佇列中插入新元素，那么如果合并之后的果子不加入原有的序列，而是另起爐灶，那么每一次合并，兩個序列中的較小值與次小值合并，原序列是有序的，而新序列中合并出的果子，先合并的一定比后合并的小，也就是說，也是有序的，
那么最后，你看這個
a
i
a_i
ai? 這么小，一定是桶排，那就變成
O
(
n
)
O(n)
O(n) 的復雜度，
Code
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#define ll long long
using namespace std;
queue<ll>q1,q2;
int t[100010];
int read()
{
int x=0;
char c=getchar();
while(c<'0'||c>'9')
{
c=getchar();
}
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x;
}
ll get()
{
ll _,__;
if(q1.empty())
{
_=q2.front();
q2.pop();
return _;
}
if(q2.empty())
{
_=q1.front();
q1.pop();
return _;
}
_=q1.front(),__=q2.front();
if(_<__)
{
q1.pop();
return _;
}
q2.pop();
return __;
}
int main()
{
int n;
n=read();
while(n--)
{
int _;
_=read();
t[_]++;
}
ll ans=0;
for(int i=1;i<=100000;i++)while(t[i]--)q1.push((ll)(i));
while(q1.size()+q2.size()>=2)
{
// puts("Amazing!");
ll _,__;
_=get();
__=get();
ans+=_+__;
q2.push(_+__);
}
printf("%lld",ans);
return 0;
}
彩蛋
Amazing！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259824.html
標籤：其他
上一篇：c++控制臺實作俄羅斯方塊
下一篇：我的大資料學習之路