B. Patchouli‘s Magical Talisman #796 div2

​​​​​​Problem - B - Codeforces

题意就是给你序列a，问最小操作可以使a里面的数都是奇数

操作1：选任意两个数合并

操作2：选一个偶数/2

这个题的思路还是很明朗的，奇数就是0，奇数+偶数必为奇数，序列a中如果存在奇数就是偶数的个数，因为偶数可以不断加到奇数上面去。但是如果都是偶数怎么办，这个地方就是贪心了，我一开始思路错了，想着全部加起来是个偶数，然后每次除以2除到奇数为止。

这个就是贪心的策略了，我这么想得需要证明这个方法的合理性啊，不证明合理性就这么想当然当然会错，比如32，要除以到奇数得5次，两个奇数偶数相加得到32，得6次。那如果取两个偶数先除以2，得到最小的操作次数到奇数，然后把另外的偶数依次加上去，当然这样更优

所以都是偶数的情况：每个数都除以2到奇数的最小操作次数求出来，先在序列里面找到一个奇数，然后把偶数依次加上去：cnt+n-1

#include<iostream> #include<vector> using namespace std; typedef long long ll; const int N=2e5+10; ll a[N]; int main(){int T;cin>>T;while(T--){ll n,even=0,od=0,sum=0,res=0x3f3f3f3f;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]%2==1) od++;if(a[i]%2==0) even++;sum+=a[i];}if(od&&even){cout<<even<<"\n";continue;}else if(even==0&&od){cout<<"0\n";continue;}else if(od==0&&even){for(int i=1;i<=n;i++){ll cnt=0;while(a[i]%2==0){cnt++;a[i]/=2;}res=min(res,cnt);}cout<<res+n-1<<"\n";}}return 0; }

总结

以上是生活随笔为你收集整理的B. Patchouli‘s Magical Talisman #796 div2的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。