ABC276 D题解

__vector__ · 2022-11-06 22:30:39 · 题解

做法

想一想除法操作的本质。

对于一个数除以 2，就是使这个数的因数 2 的数量减一。
举个简单的例子，8 分解之后有 3 个 因数 2。将其除以 2 之后，变成 4，只有 2 个因数 2 了。

除以 3 同理。

而所有数相等，实际上就是所有数的每种因数的数量分别相等。

而现在只能让每个数的因数 2 或 因数 3 的数量减少。

所以最后操作完的时候，如果取最优值，那么最终所有数的每种因数数量，都是这种因数在所有数之中出现次数的最小值。

所以先记录下因数 2 或 3 在所有数中出现的最少次数，记为 com_2,com_3。

设第 i 个数出现了 {cnt2}_{i} 次因数 2，{cnt3}_{i} 次因数 3。

答案就是 \sum_{i=1}^{n} ({cnt2}_{i} - com_2 + {cnt3}_{i} - com_3)。

那无解怎么判定？

如果两个数因数 2,3 出现的次数不同，可以通过一些操作来调整成相同。

但是如果还出现了别的因数呢？

如果还出现了别的因数，那么这个因数必须在所有的数中出现次数相同，否则无解，因为无法调整。

最后复杂度，扫一遍，扫的过程中每个数计算对数次。

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn=1005;
int n;
int a[maxn];
struct Cnt
{
    int tw,thr,els;
}cnt[maxn];
int main()
{
    scanf("%d",&n);
    int es=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        while(a[i]!=1)
        {
            if(a[i]%2 && a[i]%3 && es!=0 && a[i]!=es)
            {
                printf("-1\n");
                return 0;
            }
            if(a[i]%2&&a[i]%3)
            {
                es=a[i];
                cnt[i].els++;
                break;
            }
            if(a[i]%2==0)
            {
                a[i]/=2;
                cnt[i].tw++;
            }
            if(a[i]%3==0)
            {
                a[i]/=3;
                cnt[i].thr++;
            }
        }
    }
    for(int i=1;i<n;i++)
    {
        if(cnt[i].els!=cnt[i+1].els)
        {
            printf("-1");
            return 0;
        }
    }
    int common2=1e9,common3=1e9;
    for(int i=1;i<=n;i++)
    {
        common2=min(common2,cnt[i].tw);
        common3=min(common3,cnt[i].thr);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=cnt[i].tw-common2;
        ans+=cnt[i].thr-common3;
    }
    printf("%d",ans);
    return 0;
}