HDU - 6237 - Nightmare_ak的博客 - CSDN博客

文章价值(3) ?
阅读数(467) ?

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6237

题目大意:用最少的步数移动石子,让每一堆的石子都是一个数的倍数

解题思路:考虑最终状态每一堆必定是k*x1,k*x2,k*x3,……
那么求和则化成k*(x1+x2+x3+……),那么发现k一定是总和的因子,所以可以枚举因子,然后取模,把小的石子堆的石子移到大的石子堆上,但是会超时,发现其实枚举质因子也必定成立,这里还有一个坑点就是输入1 1,输出是0

AC代码:

#include
#include
using namespace std;

typedef long long LL;

const int MAXN = 100000 + 5;

LL prime[MAXN], divisor[MAXN];
int tot, divtot;
int getdata[MAXN], dealdata[MAXN];
bool vis[MAXN];
LL mii;

void getPrime()
{
    tot = 0;
    for (int i = 2;i < MAXN;i++)
    {
        if (!vis[i]) prime[tot++] = i;
        for (int j = 0;j < tot&&prime[j] * i < MAXN;j++)
        {
            vis[prime[j] * i] = 1;
            if (i%prime[j] == 0)
                break;
        }
    }
}

void toDivide(LL n)
{
    divtot = 0;
    for (int i = 0;i < tot&&prime[i] <= n;i++)
    {
        if (n%prime[i] == 0)
        {
            while (n%prime[i] == 0)
                n /= prime[i];
            divisor[divtot++] = prime[i];
        }
    }
    if (n > 1) divisor[divtot++] = n;
}

void toCal(int n)
{
    for (int i = 0;i < divtot;i++)
    {
        for (int j = 0;j < n;j++)
            dealdata[j] = getdata[j] % divisor[i];
        sort(dealdata, dealdata + n);
        int left = 0, right = n - 1;
        LL tmp = 0;
        while (left < right)
        {
            if (dealdata[left] == 0)
            {
                left++;
                continue;
            }
            if (dealdata[left] == divisor[i] - dealdata[right])
            {
                tmp += dealdata[left];
                left++, right--;
            }
            else if (dealdata[left] > divisor[i] - dealdata[right])
            {
                tmp += divisor[i] - dealdata[right];
                dealdata[left] -= divisor[i] - dealdata[right];
                right--;
            }
            else
            {
                tmp += dealdata[left];
                dealdata[right] += dealdata[left];
                left++;
            }
        }
        if (mii == -1) mii = tmp;
        else mii = min(mii, tmp);
    }
}

int main()
{
    getPrime();
    int t;scanf("%d", &t);
    while (t--)
    {
        int n;scanf("%d", &n);
        LL sum = 0;
        for (int i = 0;i < n;i++)
        {
            scanf("%d", getdata + i);
            sum += getdata[i];
        }
        mii = -1;
        toDivide(sum);
        toCal(n);
        if (n == 1&&getdata[0]==1) puts("0");
        else printf("%lld\n", mii);
    }
    return 0;
}




(注:此网站文章大都来自公开的博客,如有原作者发现有侵权问题,请在此留言,我们会立刻删除相关文章。)

我的评价: