累加数的贡献 CodeForces

题意：

第一行输入n，k，表示有n个数，可以进行整除2操作，要是数组有k个相等的数,最少需要几次操作。

思路：

用一个数组记录每一个数出现的次数，如果一开始大于等于k，直接输出0,否则对这n个数进行从小到大排序，对每个数进行对2整除操作，数字出现的次数加一，并且用另一个数组记录操作次数，如果过程中有一个数出现k次,在用一个数组记录操作次数，最后求最小值。

//计算每个数的贡献

#include<string.h>

#include<stdio.h>

#include<vector>

#include<algorithm>

using namespace std;

int n,k,a[200010],book[200010],sum[200010];

int main()

{

    while(~scanf("%d%d",&n,&k))

    {

        vector<int>ans;

        memset(a,0,sizeof(a));

        memset(book,0,sizeof(book));

        memset(sum,0,sizeof(sum));

        int flag=0;

        for(int i=0;i<n;i++)

        {

           scanf("%d",&a[i]);

           book[a[i]]++;

           if(book[a[i]]>=k)//记录每个数出现的次数

            flag=1;

        }

        if(flag)

        {

            printf("0\n");

            continue;

        }

        sort(a,a+n);

        for(int i=0;i<n;i++)//从小到大找

        {

            int x=a[i],t=0;

            while(x)

            {

                x=x/2;

                t++;

                book[x]++;// x 出现的次数

                sum[x]+=t;//记录得出 x 的操作次数

                if(book[x]==k)

                    ans.push_back(sum[x]);

            }

        }

        int minn=0x3f3f3f3f;

        for(int i=0;i<ans.size();i++)

            if(ans[i]<minn)

            minn=ans[i];

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

    }

    return 0;

}

巴特西

累加数的贡献 CodeForces - 1213D2

最新文章

热门文章