B. Make Them Odd

Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4)

题目链接:https://codeforces.com/contest/1277/problem/B

题目描述:

题目

思路:

其实就是给你一个数组,然后把里面的偶数通过除以二都变成奇数,计算一共需要变换几次,相同的数值除以二算作一次。思路就是先对数组按从小到大排序,用map标记一个偶数是否被变换过,因为数组已按从小到大排序,所以其他比这个数字大的数通过除以二变换到这个大小时就不再继续累计它的变换次数,不会重复累计。

代码:

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
const int maxn=2e5+5;
int a[maxn];
map<int,int>mp;
int t,n;
int fun(int x){
    int cnt=0;
    while(x%2==0&&mp[x]==0){
        x=x/2;
        cnt++;
    }
    return cnt;
}
int main(){
    #ifdef HH
    freopen("G:/input.txt","r",stdin);
    #endif // HH
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        memset(a,0,sizeof(a));
        mp.clear();
        int ans=0;
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);

            }
        sort(a,a+n);
        for(int i=0;i<n;i++){
             if(a[i]%2==0&&mp[a[i]]==0){

                ans+=fun(a[i]);
                mp[a[i]]++;
            }
        }

        printf("%d\n",ans);

    }
}
Last modification:December 14th, 2019 at 11:48 pm
如果觉得我的文章对你有用,请随意赞赏