合并果子 (贪心+排序应用) 提高组
//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;
}
//桶排序应用，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;
}
//桶排序应用，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;
}
