分配

BL_zhanggezi · 2023-04-04 13:25:04 · 题解

原题链接--->点这

问题 F: 分配
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：zhouxiaocheng

题目描述

有n颗糖果，有L个男生和U个女生。

现在要分配糖果。每个学生至少要分到1个糖果，至多分到100000个糖果。

每个男生分到的糖果数量必须相同。每个女生分到的糖果数量也必须相同。

如果L和U都不为0, 那么每个男生分到的糖果数量必须比每个女生分到的糖果数量要多。

如果按照上述的分配规则，无法分配，那么输出-1；

如果可以分配，那么输出剩下最少的糖果数量（即尽可能的把糖果分配出去，使得剩下的糖果最少）。

输入格式

多组测试数据。

第一行，一个整数G，表示有G组测试数据。1<=G<=10。

每组测试数据格式如下：

第1行，三个整数:n,L,U。 1<=n<=10^12。0<=L<=10^12, 0<=U<=10^12, L+U>0。

输出格式

共G行，每行一个整数。

输入/输出例子1

输入：

80 10 10

27 20 10

1234 15 55

1 1 0

9876543210 0 2

1234567 2323 4747

9876543210 47 0

9876543210 987654322 0

98765436210 0 9876543627

37 14 10

输出：

-1

9876343210

9871843210

987654312

9876543567

-1

==============================================================================================

这道题很简单，是个小学题，但是测试时只有方队做出来

首先，我们想到的第一个方法是暴力，代码如下

#include<bits/stdc++.h>
using namespace std;
const long long maxx=100000;
long long q,n,l,u,ans=0;
int main()
{
    cin>>q;
    while(q--)
    {
        cin>>n>>l>>u;
        ans=n;
        if(l==0)
        {
            int t=n/u;
            if(t>100000) t=100000;
            cout<<n-t*u<<endl;
        }
        else if(u==0)
        {
            int t=n/l;
            if(t>100000) t=100000;
            cout<<n-t*l<<endl;
        }
        else
        {
            for(int i=1;i<=100000;i++)
            {
                for(int j=i+1;j<=min(maxx,(n-u*i)/l);j++)
                {
                    ans=min(ans,n-u*i-j*l);
                }
            }
            if(ans==n) ans=-1;
            cout<<ans<<endl;
        }
    }

    return 0;
}

虽说暴力出奇迹，但是我们可以看到数据范围比较大，10^5 * 10^5=10^10，会超时。提交后我们只可以得到54.5%，其他点超时

那如何优化呢？

在第一个循环中我们可以直接算出每个女生分到的糖果，每个女生分到的糖果=min（100000,（总糖数-男生总共分配到的糖数）/女生人数）

这样我们就可以从二重循环优化到一重循环，代码2如下（wy哥哥教我的）：

#include<bits/stdc++.h>
using namespace std;
long long q,n,a,b;
int main()
{
    cin>>q;
    while(q--)
    {
        cin>>n>>a>>b;
        long long ans=n;
        if(a==0)
        {
            long long t=n/b;
            if(t>100000) t=100000;
            cout<<n-t*b<<endl;
        }
        else if(b==0)
        {
            long long t=n/a;
            if(t>100000) t=100000;
            cout<<n-t*a<<endl;
        }
        else
        {
            for(long long i=1;i<=100000;i++)//枚举女生
            {
                long long j=min(100000ll,(n-i*b)/a);//女生糖数
                if(i<j) ans=min(ans,n-i*b-j*a);//当女生糖数<男生糖数才算结果
            }
            if(ans==n) cout<<-1<<endl;//如果没有情况可以，就输出-1
            else cout<<ans<<endl; 
        }
    }

    return 0;
}

看上去这个代码没有什么问题，但是交上去后只有90.9%

问题出在哪呢？

当男生每个人分一个糖果和女生每个人分一个糖果时是需要糖数最小的情况，所以如果总糖数比总人数（男生人数+女生人数）小的时候，没有答案，直接输出-1，代码如下（还是wy哥哥教我的）：

#include<bits/stdc++.h>
using namespace std;
long long q,n,a,b;
int main()
{
    cin>>q;
    while(q--)
    {
        cin>>n>>a>>b;
        long long ans=n;
        if(a+b>n) cout<<-1<<endl;//总人数是否大于糖数
        else if(a==0)
        {
            long long t=n/b;
            if(t>100000) t=100000;
            cout<<n-t*b<<endl;
        }
        else if(b==0)
        {
            long long t=n/a;
            if(t>100000) t=100000;
            cout<<n-t*a<<endl;
        }
        else
        {
            for(long long i=1;i<=100000;i++)//枚举女生
            {
                long long j=min(100000ll,(n-i*b)/a);//当女生糖数<男生糖数才算结果
                if(i<j) ans=min(ans,n-i*b-j*a);
            }
            if(ans==n) cout<<-1<<endl;//如果没有情况可以，就输出-1
            else cout<<ans<<endl; 
        }
    }

    return 0;
}

分配