链接：https://ac.nowcoder.com/acm/contest/8563/A

来源：牛客网

题目描述

给一个数组，一共有n个数。
你能进行最多k次操作。每次操作可以进行以下步骤：

选择数组中的一个偶数ai，将其变成 ai/2 。

现在你进行不超过k次操作后，让数组中所有数之和尽可能小。请输出这个最小的和。

输入描述:

第一行输入两个正整数n和k，用空格隔开 

第二行输入n个正整数ai

数据范围：

1≤n≤100000，1≤k≤109

1≤ai≤10^9

输出描述:

一个正整数，代表和的最小值。

示例1

输入

5 3

2 4 8 10 11

输出

24

思路：先求和，将偶数都加入优先队列，每次取最大的偶数除以2，如果还是偶数就将它继续加入优先队列。维护最大偶数，当没有偶数或已操作m次时退出循环，此时和最小。

AC代码

  

#include<bits/stdc++.h>
using namespace std;
inline char getc(){
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
int sca()
{
    int su=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))su=su*10+c-'0',c=getchar();
    return su*f;
}
int main()
{
    int n,m,x;
    n=sca();m=sca();
    priority_queue<int>p;
    long long su=0;
    for(int i=1;i<=n;++i)
        {
            x=sca();
            if(x%2==0)
                p.push(x);
            su+=x;
        }
    while(!p.empty()&&m--)
    {
        int te=p.top()/2;
        p.pop();
        if(te%2==0)//将偶数加入优先队列，维护最大的偶数
            p.push(te);
        su-=te;//每次减少偶数的一半
    }
    printf("%lld\n",su);
}