除2!

除2!

https://ac.nowcoder.com/acm/contest/8563/A

本题需要用堆来动态管理最大的偶数。

可以用优先队列或multiset实现。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sc(x) scanf("%lld", &(x))
int main() {
    ll ans = 0, n, k, a;
    priority_queue<ll> q;
    sc(n), sc(k);
    while (n--) {
        sc(a);
        ans += a;                   //先把所有的数加起来
        if (a % 2 == 0) q.push(a);  //所有的偶数进优先队列
    }
    while (!q.empty() && k--) {  //还有偶数而且次数没用完
        ll now = (q.top() / 2);
        ans -= now;  //执行一次操作
        if (now % 2 == 0) q.push(now);
        q.pop();
    }
    printf("%lld\n", ans);
}

学习@19zhaoyang的multiset写法:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sc(x) scanf("%lld", &(x))
int main() {
    ll n, m, x;
    sc(n), sc(m);
    multiset<ll, greater<ll>> st;
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        sc(x);
        if (x & 1)
            ans += x;  //统计奇数
        else
            st.insert(x);  //加入偶数
    }
    while (m && st.size()) {
        int now = *st.begin();
        st.erase(st.begin());  //删除堆顶
        if (now & 1)
            ans += now;  //奇数不消耗次数,加入答案
        else
            st.insert(now / 2), --m;
    }
    for (auto& it : st) ans += it;  //相当于用const &遍历,更高效
    printf("%lld\n", ans);
    return 0;
}
算法竞赛之路 文章被收录于专栏

整理、记录算法竞赛的好题

全部评论

相关推荐

10-13 16:58
门头沟学院 Java
面了100年面试不知...:一周七天,一天去一家上班😍😍😍
点赞 评论 收藏
分享
评论
3
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务