合并果子 (貪心+排序應(yīng)用) 提高組
//n==10**7 timeout
#include<bits/stdc++.h>>
using namespace std;
int main(){
? ? std::ios_base::sync_with_stdio(false);
? ? cin.tie(0);? ??
? ? int n;
? ? cin>>n;
? ? multiset<long long> a;
? ? for(int i=0;i<n;i++){
? ? ? ? long long tmp;
? ? ? ? cin>>tmp;
? ? ? ? a.insert(tmp);
? ? }
? ? long long ans=0;
? ? while(a.size()>=2){
? ? ? ? long long x=*a.begin();
? ? ? ? a.erase(a.begin());
? ? ? ? long long y=*a.begin();
? ? ? ? a.erase(a.begin());
? ? ? ? ans+=x+y;
? ? ? ? a.insert(x+y);
? ? }
? ? cout<<ans<<endl;
? ? return 0;
}
//桶排序應(yīng)用，O(n), 兩個有序隊列的歸并O(m+n)
#include <iostream>
#include <queue>
typedef long long ll;
using namespace std;
queue <ll> q1;
queue <ll> q2;
ll to[100005];
signed main() {
? ? std::ios_base::sync_with_stdio(false);
? ? cin.tie(0);? ??
int n;
cin>>n;
for (int i = 1; i <= n; ++i) {
ll a;
cin>>a;
to[a] ++;
}
for (int i = 1; i <= 100000; ++i) {
while(to[i]) {
to[i] --;
q1.push(i);
}
}
ll ans = 0;
for (int i = 1; i < n; ++i) {
ll x , y;
if((q1.front() < q2.front() && !q1.empty()) || q2.empty()) {
x = q1.front();
q1.pop();
}
else {
x = q2.front();
q2.pop();
}
if((q1.front() < q2.front() && !q1.empty()) || q2.empty()) {
y = q1.front();
q1.pop();
}
else {
y = q2.front();
q2.pop();
}
ans += x + y;
q2.push(x + y);
}?
cout<<ans<<endl;
return 0;
}?
//桶排序應(yīng)用，O(n), 兩個有序隊列的歸并O(m+n)
#include <cstdio>
#include <queue>
#define int long long
using namespace std;
queue <int> q1;
queue <int> q2;
int to[100005];
void read(int &x){?
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
signed main() {
int n;
read(n);
for (int i = 1; i <= n; ++i) {
int a;
read(a);
to[a] ++;
}
for (int i = 1; i <= 100000; ++i) {
while(to[i]) {
to[i] --;
q1.push(i);
}
}
int ans = 0;
for (int i = 1; i < n; ++i) {
int x , y;
if((q1.front() < q2.front() && !q1.empty()) || q2.empty()) {
x = q1.front();
q1.pop();
}
else {
x = q2.front();
q2.pop();
}
if((q1.front() < q2.front() && !q1.empty()) || q2.empty()) {
y = q1.front();
q1.pop();
}
else {
y = q2.front();
q2.pop();
}
ans += x + y;
q2.push(x + y);
}?
printf("%lld" , ans);
return 0;
}?
