Equal Numbers Gym - 101612E 思维

题意：

给你n个数vi，你有k次操作。每一次操作你可以从n个数里面挑一个数，然后使得这个数乘于一个正整数。操作完之后，这n个数里面不同数的数量就是权值。你要使得这个值尽可能小。

题解：

如果a%b==0 && a!=b

　　b%c==0 && b!=c

那么如果我们进行操作的话，肯定是把c变成a，因为这样消耗的最小操作数最少

我们最后的答案只需要在两种情况中取最小值就可以了

1、我们把n个数都往n个数的公倍数上变

2、如果这n个数里面出现了上面所示的a、b、c的情况，那么我们就把b、c这些数都往a上变

过程：

因为题目求的是操作完之后不同数的数量，那么我们首先记录一下每一个数的出现次数

然后在提前处理一下每一个数的倍数是否在这n个数里面

然后按照每一个数出现的次数排序。为什么？给你一个序列

1 1 2 4

我们如果只有一个操作，那么肯定是把2变成4.这样的话答案就是2

这就意味着，我们要使得1变成4的话，那么只有操作数大于等于3的时候才对最后的结果造成影响

之后就模拟就可以了

AC代码：

/*

有两种操作，要么是把一种数全部变成他的倍数（尽量大且存在的倍数），要么是将尽量多种类的数变成所有数的公倍数。

那么我们只需要维护出每种数是否存在其倍数，就只能这种数能否进行第一种操作。

只要对每个数因数分解，然后给因数打上标记，就可以知道每个数是否存在其倍数了。复杂度n*sqrt(t),t代表数据范围。

*/

#include <algorithm>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 1e6 + 5;

const int INF=0x3f3f3f3f;

const int mod = 1000000007;

int v[maxn],num[maxn],vis[maxn],que1[maxn],que2[maxn];

int main()

{

    freopen("equal.in","r",stdin);

    freopen("equal.out","w",stdout);

    int n;

    scanf("%d",&n);

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

    {

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

        num[v[i]]++;

    }

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

    {

        int tmp=v[i];

        if(tmp!=1) vis[1]=1;

        int ends=sqrt(tmp);

        for(int j=2;j<=ends;++j)

        {

            if(tmp%j==0)

            {

                vis[j]=1;

                vis[tmp/j]=1;

            }

        }

    }

    int pos1=0,pos2=0;

    for(int i=1;i<=1000000;++i)

    {

        if(num[i]==0) continue;

        int tmp=i;

        if(vis[tmp])

        {

            que1[pos1++]=num[tmp];

        }

        que2[pos2++]=num[tmp];

    }

    sort(que1,que1+pos1);

    sort(que2,que2+pos2);

    //printf("%d****%d %d\n",pos1,que1[0],que1[1]);

    int ans1=0,ans2=0,tmp1=0,tmp2=0;

    printf("%d ",pos2);

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

    {

        tmp1+=1;

        while(tmp1>=que1[ans1] && ans1<pos1)

        {

            tmp1-=que1[ans1];

            ans1++;

        }

        tmp2+=1;

        while(tmp2>=que2[ans2] && ans2<pos2)

        {

            tmp2-=que2[ans2];

            ans2++;

        }

        if(i!=n)

            printf("%d ",pos2-max(ans1,ans2-1));

        else printf("%d\n",pos2-max(ans1,ans2-1));

    }

    return 0;

}

巴特西

Equal Numbers Gym - 101612E 思维

最新文章

热门文章