当前位置：首页 > article >正文

牛客（除2！）

article 2024/9/19 9:06:40

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

题目描述

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

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

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

思路：

遍历一遍数组，偶数保存在一个大堆中，奇数直接加在结果中。然后每次从堆顶提取元素，即当前最大的偶数，对其除以2，若是奇数则直接加入结果中，若是偶数则重新放入大堆中。

注意:本题结果可能超过INT的范围，因此用long long。


#include<algorithm>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>

using namespace std;

struct cmp
{
    bool operator()(int a,int b)
    {
        return a<b;
    }
};

int main()
	{ 
    int n,k;
    cin>>n>>k;
    priority_queue<int,vector<int>,cmp>qn;
    long long ret=0;
    for(int i=0;i<n;i++)
    {
        int kk=0;
        cin>>kk;
        if(kk%2==0)
            qn.push(kk);
        else
            ret+=kk;
    }
     
    while(k--&&qn.size())
    {
        int kk=qn.top()/2;
        qn.pop();
        if(kk%2==0)
            qn.push(kk);
        else
            ret+=kk;
    }
    while(qn.size())
    {
        ret+=qn.top();
        qn.pop();
    }
    cout << ret;

return 0;
}

查看全文

http://www.kler.cn/news/294969.html