CF1609A Divide and Multiply

CF1609A Divide and Multiply

感觉自己真的有点蠢，有时候一个思路自己就是想不到，一直在那里走迷宫还走不出来，或许是刷的题目还不够吧，等待开悟。先说一下这道题吧。

本题大意是有一种 *** 作，找一个偶数除以2的同时再找一个数*2，这种 *** 作可以进行无数次，问进行n次 *** 作后这个数列的和最大是多少。

刚开始的想法是模拟。

1.将能取出2的数先全部去一遍，例如8，就可以取3次，取完后是1，6只能取出一次，去完后是3吗，记录两次取出2的个数，分为奇数和偶数ans1,ans2

2.是找出最大的偶数和最大的奇数，然后偶数ans1减去最大偶数的次数，奇数ans2不变

3.累加进行 *** 作后的数列和

4.将奇数的最大值进行pow(2,maxx2),偶数进行pow(2,maxx1)，分别求和看那个和最大就输出哪个

刚开始的错误思路就是这个样子，我还觉得没有问题，但是2 6 8这种情况肯定是优先拆8，累乘6，但是按上面的思路是累成8，这样就有问题了，还不知道怎么解决。

参考了大佬的代码发现压根就没有那么麻烦

新思路

1.将所有的能取2的统统取一遍，再进行一次排序。

2，找出最大的进行累乘，例如a[n]是最大值，则进行pow(2,ans)+（1····n-1）a[i]这就是最终答案

这个写法避免了我那种找不到累加哪个最划算的问题，刚开始就算是最划算的数被除2，但是后来的pow又会乘上来，所以问题不大，上代码，

#include
using namespace std;
#define ll long long
int n,t;
ll s[20];
int main() {
	cin>>t;
	while(t--) {
		cin>>n;
		for(int i=1; i<=n; i++)
			cin>>s[i];
		ll res=0;
		for(int i=1; i<=n; i++) {
			while(s[i]%2==0) {
				s[i]/=2;
				res++;
			}
		}
		sort(s+1,s+1+n);
		s[n]*=pow(2,res);
		ll sum=0;
		for(int i=1; i<=n; i++) {
			sum+=s[i];
		}
		cout< 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5657463.html