CF792E Colored Balls

题目大意：将n个数分解成若干组，如4 = 2+2， 7 = 2+2+3，保证所有组中数字之差<=1。

首先我们能想到找一个最小值x，然后从x+1到1枚举并check，找到了就输出。这是40分做法。

能不能优化？我们发现，若k合法，那么x%k==0或x%(k+1)==0或x%(k-1)==0。

所以枚举倍数就行了，利用贪心找到了就输出。

代码：

#include<cstdio>

#include<algorithm>

using namespace std;

#define ll long long

int n;

ll a[],mn=0x3f3f3f3f;

bool cmp(ll x,ll y)

{

    return x<y;

}

void check(ll k)

{

    if(!k)return ;

    ll ret = ;

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

    {

        if(a[i]<k-)return ;

        int cnt = a[i]/k+(a[i]%k!=);

        if(a[i]%k==)

        {

            ret+=cnt;

            continue;

        }

        if(k*cnt-a[i]>cnt)return ;

        ret+=cnt;

    }

    printf("%I64d\n",ret);

    exit();

    return ;

}

int main()

{

//    freopen("C.in","r",stdin);

//    freopen("C.out","w",stdout);

    scanf("%d",&n);

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

    {

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

        mn=min(mn,a[i]);

    }

    for(int i=;i<=mn;i++)

    {

        check(mn/i+);

        check(mn/i);

        check(mn/i-);

    }

    fclose(stdin);

    fclose(stdout);

    return ;

}

巴特西

CF792E Colored Balls

最新文章

热门文章