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

容易发现，在

n

确定的时候，由于每个人做的题数不同，我们让第

i

个人做

i

道题，

n

个人就做

1 + 2 + 3 + 4 + 5 + \cdots + (n-1) + n = n \times (n + 1) \div 2

，如果

m

小于这个值，则不能够分配。

接下来，我们处理最大差。

我们让前

n-1

个人中的第

i

个人做

i

道题，最后一个人做剩下的题，可以使得差值最大。

其中，前

n-1

个人一共做了

(n-1) \times n \div 2

。

最后，我们处理最小值。

我们先让

n

个人中的第

i

个人做

i

道题，剩下题目则平均分配给每个人，由于平均分后仍然有剩余，我们让最后几个人依次多做一道题，也就是说，第

n

个人还应该多做一道题。

特别注意，需要开

CPP

unsigned long long

注释版完整代码：

CPP

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll sum1(ll n){
	return n*(n+1)/2;
}
/*
n 个人最少完成题数为 sum1(n)，如果 m 小于 sum1(n)，则输出 -1 
*/
bool v(ll n,ll m){
    return m<sum1(n);
}

/*
max:让 n - 1 个人分配的 1 , 2 , …, n-1 题，剩下的全给第 n 个人
*/
ll mx(ll n, ll m){
    ll s=sum1(n-1);
    ll x=m-s;//第n个人分配的题数
    return x-1;
}

/*
min:在基础分配 1 , 2 , …, n 的前提下，将剩余题数平均分配
*/
ll mn(ll n, ll m){
    ll s=sum1(n);//分配题数
    ll d=m-s;//剩余题数
    ll k=d/n;//每人平均可额外分配的题数
    ll r=d%n;//分配后剩余的题数 
    ll mi=1+k;//基础最小值(1) + 平均额外分配数k
    ll ma=n+k+(r>0?1:0);//基础最大值(n) + 平均额外分配数k （如果有剩余题数则+1） 
    return ma-mi;
}

int main(){
    int T;
    cin>>T;
    while(T--){
        ll n,m;
        cin>>n>>m;
        if(v(n,m)){
            puts("-1 -1");
            continue;
        }
        cout<<mx(n,m)<<" "<<mn(n,m)<<"\n";
    }
    return 0;
}

无注释代码：

CPP

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll sum1(ll n){return n*(n+1)/2;}
bool v(ll n,ll m){return m<sum1(n);}
ll mx(ll n, ll m){ll s=sum1(n-1),x=m-s;return x-1;}
ll mn(ll n, ll m){ll s=sum1(n),d=m-s,k=d/n,r=d%n,mi=1+k,ma=n+k+(r>0?1:0);return ma-mi;}
ll n,m,_;
int main(){
    cin>>_;
    while(_--){
        cin>>n>>m;
        if(v(n,m)){cout<<"-1 -1\n";continue;}
        cout<<mx(n,m)<<" "<<mn(n,m)<<"\n";
    }
    return 0;
}

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

文章操作

相关推荐

评论

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