当前位置: 代码迷 >> 综合 >> Random Teams
  详细解决方案

Random Teams

热度:69   发布时间:2023-11-23 19:11:14.0

Description

n个人他们两两之间都是朋友,把他们分到m间房间中,每间房间中至少有一个人。
问分配后,朋友最少是多少对,最多是多少对。

Input

输入两个整数n和m,有(1<=m<=n<=10^9)。

Output

每行输出两个整数Kmin和Kmax。

Sample Input

6 3
Sample Output

3 6

思路:
猜例子大致得到当把所有人集中起来时(满足每个房间都有一个,其他集中起来),朋友的对数是最多的,而最少的就是平均分配出去。
最多的计算:
人数减去房数+1,剩下的N个人里CN,2,即n*(n-1)/2
最少的计算:
平均分配(当然不一定能完全平均),每个房间M个人,CM,2,即m*(m-1)/2,每个房间的加起来

#include<stdio.h>
int main(){
    long long i,j,min,max,a,b;while(~scanf("%lld%lld",&a,&b)){
    i=a/b;if(i==1){
    min=a-b;max=(a-b+1)*(a-b)/2;}else{
    min=(b-(a-i*b))*i*(i-1)/2+(a-i*b)*(i+1)*i/2;max=(a-b+1)*(a-b)/2;}printf("%lld %lld\n",min,max);	}return 0;
}
  相关解决方案