除2题号NC213140时间限制C/C/Rust/Pascal 1秒其他语言2秒空间限制C/C/Rust/Pascal 256 M其他语言512 M64bit IO Format: %lld题目描述给一个数组一共有 n 个数。你能进行最多 k 次操作。每次操作可以进行以下步骤选择数组中的一个偶数 ai将其变成 ai/2。现在你进行不超过 k 次操作后让数组中所有数之和尽可能小。请输出这个最小的和。输入描述:第一行输入两个正整数 n 和 k用空格隔开第二行输入 n 个正整数 ai数据范围1≤n≤1000001≤k≤1091≤ai≤109输出描述:一个正整数代表和的最小值。示例1输入5 3 2 4 8 10 11输出24说明对8操作2次对10操作1次最后的数组是2 4 2 5 11。可以证明这样的操作是最优的。重要信息1、选择只能选择偶数 2、要限制在k次内 3、所有数都是正整数要判断是否为偶数每次除2必须选偶数的最大值。每次除2后最大值可能发生改变所以每次都要找一下最大值找k次中间当找不到时就代表没有偶数了那么就不用后续的查找了。所以先设计一个查找偶数最大值的接口调用就把最大偶数做除二处理有除2操作返回true没有除二操作返回false。思路一1、寻找K次最大偶数除二当找不到时说明没有偶数了可以提前结束寻找。2、求和#includeiostream#includevector#includealgorithmusingnamespacestd;boolGetMaxOS(vectorintv)// 使用引用直接就判断就改了{intmax0;for(autoe:v){if(e%2!0)continue;// 如果不为偶数就继续判断下一个if(emax)// 如果为偶数要判断是不是最大值{maxe;}}// 走到这里如果max为0说明没有偶数了if(max0)returnfalse;// 走到这里说明存在最大偶数automaxofind(v.begin(),v.end(),max);(*maxo)(*maxo)/2;returntrue;}intmain(){intn,k;cinnk;vectorintv;for(inti0;in;i){inttemp0;cintemp;v.push_back(temp);}while(k){// 获取每次偶数的最大值如果没获得返回-1获得了返回下标if(!GetMaxOS(v)){break;}k--;}// 取和intsum0;for(constautoe:v){sume;}coutsum;return0;}自测用例通过提交时不通过说明还需要优化将所有的int改成long long有部分示例可以通过说明要考虑所加和超过int的情况#includeiostream#includevector#includealgorithmusingnamespacestd;boolGetMaxOS(vectorlonglongv)// 使用引用直接就判断就改了{longlongmax0;for(autoe:v){if(e%2!0)continue;// 如果不为偶数就继续判断下一个if(emax)// 如果为偶数要判断是不是最大值{maxe;}}// 走到这里如果max为0说明没有偶数了if(max0)returnfalse;// 走到这里说明存在最大偶数automaxofind(v.begin(),v.end(),max);(*maxo)(*maxo)/2;returntrue;}intmain(){longlongn,k;cinnk;vectorlonglongv;for(inti0;in;i){longlongtemp0;cintemp;v.push_back(temp);}while(k){// 获取每次偶数的最大值如果没获得返回-1获得了返回下标if(!GetMaxOS(v)){break;}k--;}// 取和longlongsum0;for(constautoe:v){sume;}coutsum;return0;}思路二堆贪心1、上去直接求和sum同时将偶数备份到priority_queue里存到大堆得以自动排序方便获取偶数最大值2、a.如果没有堆里一开始没有值/再除2的过程中用完了就不需要继续除二操作了到步骤3。b.如果堆里有值先将堆顶值除2的值temp保留下来然后删除堆顶元素接下来判断被删除的堆顶值除2后是否还是偶数其实值就是temp是就将temp继续存到堆里然后用(和-temp)3、上述步骤结束就得到了最终的sum。#includeiostream#includequeueusingnamespacestd;// 使用long long存数据typedeflonglongLL;// 将所有偶数存到大堆里这样能保证每次拿到的是最大的偶数priority_queueLLheap;intmain(){LL n0,k0;cinnk;LL x0,sum0;for(inti0;in;i){cinx;// 先算出所有数据的和sumx;// 同时相当于将所有偶数备份了一遍还可以自动按照从大到小的顺序排序if(x%20)heap.push(x);}// 进行k次最大偶数除2操作while(k){// 如果连偶数都没有了就不需要除2操作了if(!heap.size()){break;}// 走到这里说明存在偶数取到堆顶元素除二先存起来LL theap.top()/2;heap.pop();// 删掉堆顶元素sum-t;// 减去除2的值// 判断除2后的值是否还是偶数如果是就继续存到堆里if(t%20)heap.push(t);k--;}coutsumendl;return0;}