题解：P14166 题目分配 (divide)

· · 题解

题目描述

参见原题，link

思路及做法

题目给定 2 \le n,m \le 10^{18}，而由于每人分配到的题目数量各不相同且不能有人一题不做，所以至少要有 \frac{n(n+1)}{2} 道题给大家做才行。

所以 n>2 \times 10^9 时无法分配，可以直接特判掉输出-1 -1；若 \frac{n(n+1)}{2}>m 同样无法分配。

可以证明当 \frac{n(n+1)}{2} \le m 时一定存在合法的分配方案。以下在此情况下讨论。

不合理度的最大值

最大值比较简单。分配题目数的最小值最小为 1，接下来为了让分到题目最多的人题目最多，其余 (n-1) 个人均应分配尽可能少的题目，即 1,2,3,...,n-1。

最后分配题目数的最大值为 m- \frac{(n-1)n}{2}，不合理度的最大值为 m-\frac{(n-1)n}{2} -1。

不合理度的最小值

对于最小值，我们先取定每人 1,2,...,n 道题，称其为原始状态，再考虑剩下的题如何分配。记 K=m-\frac{n(n+1)}{2} 表示当前未分配的题目数。

最理想的情况下，不合理度为 n-1。此时每人分到的题目数恰好为连续的 n 个正整数。这种情况必然可以看作是原始状态下每人再额外多分配相同数量的题目得到的。这等价于,当且仅当 n\mid K 时可以取到 n-1。

若 n \nmid K，则最小值取不到 n-1，转而考虑能否取到 n。事实上，这是一定可以取到的。记 k=K \bmod n，则 n\mid K-k，从而这 (K-k) 道题可以均分给所有人。接下来按照分配题数排序，从最多的人开始每人多分配 1 题，分完为止。此时分配题数最少的没有变，最大的增加了 1，所以取到了不合理度为 n。

综上，不合理度的最小值当 n\mid K 时为 n-1，否则为 n。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll n,m;    //记得开long long
        cin>>n>>m;
        if(n>2e9) cout<<"-1 -1\n";    //特判
        else if(n*(n+1)/2>m) cout<<"-1 -1\n";    //特判
        else cout<< m-(n-1)*n/2-1 <<" "<< n-1+((m-n*(n+1)/2)%n==0 ? 0 : 1) <<"\n";
    }
    return 0;
}

提交记录

2025.10.06