欢迎光临散文网 会员登陆 & 注册

合并果子 (贪心+排序应用) 提高组

2022-10-24 12:36 作者:信奥赛USACO郑老师  | 我要投稿

//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;


合并果子 (贪心+排序应用) 提高组的评论 (共 条)

分享到微博请遵守国家法律