感觉自己真的有点蠢,有时候一个思路自己就是想不到,一直在那里走迷宫还走不出来,或许是刷的题目还不够吧,等待开悟。先说一下这道题吧。
本题大意是有一种 *** 作,找一个偶数除以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又会乘上来,所以问题不大,上代码,
#includeusing 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< 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)