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

· · 题解

验题人题解。这题我验了十几分钟，没想到吧。

前置知识

### 解题思路 判断无解： - 让 $n$ 个人分别做 $\{1,2,\dots,n\}$ 题，然后让做题最多的人完成剩下的题是一种可行的方案。 - 因此 $n$ 个人至少要写 $\frac{n(n+1)}{2}$ 题。 - 只要总题数大于等于它，一定有解。 - 只要总题数小于它，一定无解。 尝试构造办法使得不合理度最大： - 令做题最少的人做 $1$ 题。一定不劣。 - 为了令做题最多的人做得尽量多，其他人应该腾出题给他做。 - 当前 $n-1$ 个人分别做 $\{1,2,\dots,n-1\}$ 题时，没有更多的题可以分配给做题最多的人了。 - 因此做题方案形如 $\{1,2,\dots,n-1,K\}$。 - $K=m - \frac{n(n-1)}{2}$。最大的不合理度即为 $K-1$。 尝试构造方法使得不合理度最小： - 先给第 $i$ 个人分配 $i$ 个题。 - 考虑在这个形势下再给某人分配一道题。显然分配给**做题最少的能再做一道题的人**。 - $\{1,2,\dots,n-3,n-2,n-1,n+1\}$。 - $\{1,2,\dots,n-3,n-2,n,n+1\}$。 - $\{1,2,\dots,n-2,n-1,n\}$。 - $\dots

代码展示

为了防止分类讨论，这里使用了 __int128。

它是一种在 64 位操作系统下可以使用的类型，能够存储 -2^{127} 到 2^{127}-1 范围内的数据。但是它不支持用 cin 或 cout 读入或输出。

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