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

· · 题解

题意

较为简单，建议直接看题面，写几个注意事项： 1.注意数据范围，要开long long 2.无解要输出两个-1

思路

判断有没有解

人们最少需要的题目量若比给的题目量大则无解，否则有解，最少的状态就是从1开始依次递增，如：

1 2 3 4 5 6 …… n

总量为 (n+1) \times n/2(欧拉公式) 接着再把总量与m比较即可。

最大值

不合理度的最大值一定是让最小值尽可能小，最大值尽可能大，最小肯定是1(因为题目给了没人最少一道)，那最大值要最大就等同于让除了他的所有数最小，分配如下

1 2 3 4 …… max

然后只用算出max再用它减一就好了。

最小值

不合理度的最小值就是要让最小值和最大值尽可能的接近，那一个个排上去就是最好的了，如：

1 2 3 4 5……

但题目一般没那么凑巧，不过全体加一可以让不合理度不变，那就先让所有人先依次加题加到题目不够了，再处理，如果没有剩余题目自然最好，那答案就是人数减一，否则只需要在中间空上一位再剩下加一就是最优解，答案为人数。

不会的见代码

代码

#include<bits/stdc++.h>
#define int unsigned long long//不开long long见祖宗 ，开了还要见祖宗，记得加unsigned 
using namespace std;
signed main(){
    int T;//数据组数 
    cin>>T;
    for(int i=1;i<=T;i++){
        int n,m;
        cin>>n>>m;
        int sum=(n+1)*n/2;//最少总题目数
        if(sum>m){
            cout<<"-1 -1"<<endl;
            continue;
        } //判无解
        cout<<m-sum+n-1<<" ";//最小值
        if((m-sum)%n==0){
            cout<<n-1<<endl;
        }else{
            cout<<n<<endl;
        }//最大值 
    }
    return 0;
}