题解：P14166 [Algo Beat Contest 002.5 A] 题目分配 (divide)

· · 题解

题目传送门

1 具体做法

1.1 无解

不难发现，如果每道题都恰好让 1 名队员去做，而且要求所有人分配到的题目数量必须互不相同，且每个人至少分配到 1 题，那 m 最小为 \sum\limits_{i=1}^{n}=\frac{n(n+1)}{2} 。所以如果 m 小于 \frac{n(n+1)}{2} 输出-1 -1即可。

1.2 最大值

为了符合题目要求，我们让第 i 个人做 i 道题。此时会剩余 m-\frac{n(n+1)}{2} 道题，为了让最大值与最小值差最大就让第 n 个人全部做完即可。太邪恶了。

1.3 最小值

同上，为了符合题目要求，我们让第 i 个人做 i 道题。此时会剩余 m-\frac{n(n+1)}{2} 道题。这时，我们不能让第 1 个人与第 n 个人做的题目数量拉开太大的差距，所以我们让剩下的 m-\frac{n(n+1)}{2} 道题平均分配给 n 个人。如果无法平均分，那就让分剩下的题给编号靠后的人每人 1 题即可。

2 代码

2.1 无解

一个判断即可。

if(n>=2000000000||m<n*(n+1)/2)cout<<"-1 -1\n";

2.2 最大值

为了防止溢出，对与 n 的奇偶有不同的公式：

if(n&1)cout<<m-(n-1)/2*n-1;
else cout<<m-n/2*(n-1)-1;

2.3 最小值

同上，为了防止溢出，对与 n 的奇偶有不同的公式：

if(n&1)cout<<n-1+((m-(n+1)/2*n)%n?1:0)<<"\n";
else cout<<n-1+((m-n/2*(n+1))%n?1:0)<<"\n";

2.4 ACcode

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int t,n,m;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        if(n>=2000000000||m<n*(n+1)/2)cout<<"-1 -1\n";
        else if(n&1)cout<<m-n/2*(n-1)-1<<" "<<n-1+((m-n/2*(n+1))%n?1:0)<<"\n";
        else cout<<m-(n-1)/2*n-1<<" "<<n-1+((m-(n+1)/2*n)%n?1:0)<<"\n";
    }
}

已做防伪处理，请勿复制！！！