分析
贪心思路:每次选一个偶数出来,如何才能使总和的减少量最大?明显,取出最大的那一个偶数,除二,直到所有的数不能被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; }