域名买卖网站,网站英文域名是什么,wordpress作品集,seo搜索引擎工具题目链接#xff1a;除2#xff01; 1.题目解析
1#xff1a;想让数组所有数之和尽可能小#xff0c;肯定有个想法#xff0c;就是我每次选数组中偶数的时候#xff0c;我必定挑一个最大的#xff0c;因为我挑一个最大的出来#xff0c;把它变成一半#xff0c;这个时…题目链接除2 1.题目解析
1想让数组所有数之和尽可能小肯定有个想法就是我每次选数组中偶数的时候我必定挑一个最大的因为我挑一个最大的出来把它变成一半这个时候总和减小肯定是最多的
2我们待会儿是要求所有数组元素的和数据量有100,000这么大每个数有10的九次方这么大有可能超出int的范围所以我们要用long long来存这个数看到数据范围的时候大家一定要小心一点我们是用int还是用long long
结合示例最多进行三次操作把10变成5接下来最大的值是8把8变成4这两个4随便挑一个出来变成2这时它们的加起来是24251124
2.算法原理
解法每次挑选出当前数组中最大的偶数然后减小一半利用大根堆实现
代码
#include iostream
#include queue
using namespace std;typedef long long LL;
int n, k;
priority_queueint heap; //默认是大根堆int main()
{cin n k;LL sum 0;for (int i 1; i n; i){int x; cin x;sum x;//偶数进堆if (x % 2 0) heap.push(x);}while (heap.size() k--){int t heap.top() / 2;heap.pop();sum - t;//除完后可能还是偶数//用%不用除比如10/25,5/22if (t % 2 0) heap.push(t);}cout sum endl;return 0;
}
