除2!

分析

贪心思路:每次选一个偶数出来,如何才能使总和的减少量最大?明显,取出最大的那一个偶数,除二,直到所有的数不能被2整除或是k=0

代码

/*
(写点什么吧...)
*/
#include<bits/stdc++.h>

#define R register
#define ll long long
#define inf INT_MAX

using namespace std;

const int N=1e5+10;

int n,k;ll ans;

priority_queue<ll>q;

int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++)
    {
        ll x;scanf("%lld",&x);
        if(x%2) ans+=x;
        else q.push(x);
    }

    while(k)
    {
        if(!q.size()) break;
        ll u=q.top();q.pop();
        if(u%2) ans+=u;
        else u/=2,q.push(u),k--;
    }

    while(q.size()) ans+=q.top(),q.pop();

    printf("%lld\n",ans);

    return 0;
}